[go: up one dir, main page]
Scribd
Upload
65 views1 page

Tutorial Sheet 1

This document contains 14 problems related to graph theory and algorithms. The problems cover topics such as determining the number of vertices and edges in a graph, proving properties of graphs based on degree and connectivity, constructing graphs based on given conditions, and drawing all possible simple graphs on a given number of vertices. The full range of graph theory and algorithm concepts are represented in this tutorial worksheet.

Uploaded by

Ahammad Mostafa Hossain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
65 views1 page

Tutorial Sheet 1

This document contains 14 problems related to graph theory and algorithms. The problems cover topics such as determining the number of vertices and edges in a graph, proving properties of graphs based on degree and connectivity, constructing graphs based on given conditions, and drawing all possible simple graphs on a given number of vertices. The full range of graph theory and algorithm concepts are represented in this tutorial worksheet.

Uploaded by

Ahammad Mostafa Hossain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Graph Theory and Algorithms

Tutorial Sheet-1
(1) Let M = (aij ) be an n×m matrix. Consider a graph G whose vertices are the entries
of M and two vertices are adjacent if they lie in the same row or same column. Then

(a) Find the total number of vertices of G?


(b) Is G a regular graph? If yes, then find the degree of regularity.
(c) Find the total number of edges of G.

(2) In any group of n persons (n ≥ 3), show that there are at least two with the same
number of friends.

(3) Prove that if a graph has exactly two vertices of odd degree then there must be a
path in the graph joining them.

(4) Prove or disprove: (i) If every vertex of a simple graph G has degree 2 then G is a
cycle.
(ii) A closed trail with all its vertices of degree 2 is a cycle.

(5) If G is a simple graph with n vertices and the minimum degree δ(G) ≥ n−1
2
then
prove that G is connected.

(6) Show by means of an example that the condition δ(G) ≥ n−2


2
for a simple graph G,
need not imply that G is connected.

(7) Let G be a graph in which there is no pair of adjacent edges. What can you say
about the degrees of the vertices in G.

(8) Let G be a graph with n vertices and e edges. Let m be the smallest positive integer
such that m ≥ 2e
n
. Prove that G has a vertex of degree at least m.

(9) Let G be a graph with n vertices and exactly n − 1 edges. Prove that G has either
a pendant vertex or an isolated vertex.

(10) Prove that in a group of six people, there must be three people who are mutually
acquainted or three people who are mutually non-acquainted.

(11) Prove that if a simple graph G is not connected then its complement is connected.

(12) Let G be a simple graph with δ(G) ≥ k. Show that: (i) G contains a path of length
at least k.
(ii) If k ≥ 2 then G contains a cycle of length at least k + 1.

(13) Draw all possible simple non-isomorphic graphs on four vertices.

(14) Let S = {1, 2, 3, 4, 5}. Construct a graph G whose vertex set is the collection of all
2-subsets of S and two vertices are adjacent in G if and only if the corresponding
2-subsets are disjoint. Prove that G is isomorphic to the Petersen graph.

You might also like