US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

(c) Depends on p
(d) None of these

13. Which of the following statement is true ?

(a) In a simple graph there are at most two vertices of equal degree
(b) In a simple graph there at least two vertices of equal degree
(c) Degree of vertices are all distinct
(d) None of these

14. Disconnected graph G without self loops and parallel edges with p vertices and k-components
can have almost
(n−k)(n−k+1)
(a) 2
edges
n−k)2
(b) 4
edges
(c) n(n − 1) edges
(d) None of these

15. If Bipartite graph G = (X, Y, E) is k-regular (k > 0), then

(a) |X| = |Y |
(b) |X| > |Y |
(c) |X| < |Y |
(d) None of these

Practical 4C.1: Handshaking Lemma and Isomorphism

Descriptive Questions 4C.1

1. A certain graph G has order 14 and size 27. The degree of each vertex of G is 3, 4, or 5. There
are six vertices of degree 4. How many vertices of G have degree 3 and how many have degree
5?

2. Suppose we have a graph G = (V, E), in which every vertex has degree 3, 5, or 7. If G has 14
vertices and 29 edges, and has twice as many vertices of degree 3 as vertices of degree 5, how
many vertices of each degree does it have?

3. If a simple graph G has two pendant vertices prove that G has at most two pendant vertices.
Give an example of a graph G such that both G and G have exactly two pendant vertices.

4. Let G be a (p, q) graph all of whose vertices have degree k or k + 1. If G has t > 0 vertices of
degree k, show that t = p(k + 1) − 2q.

6.3
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

5. Show that the number of edges of a simple graph with k components cannot exceed (n−k)(n−k+1)
2
.
(n−k)(n−k+1)
Give an example of a disconnected simple graph having k components, n vertices and 2
edges.

6. Show that in a party of 6 or more people, either there are 3 persons who know one another or
there are three persons who do not know one another.

7. If G and H are isomorphic graphs , then show that the degree sequence of the vertices of G are
the same as the degree sequence of the vertices of H.

8. Show that in any group of n persons (n ≥ 2), there are at least two with the same number of
friends.

9. Prove that the following graphs are isomorphic using their adjacency matrices.
a)

b)

10. Let G and H be two isomorphic graphs. Show that

(a) degree sequences of G and H are same.
(b) G is connected if and only if H is connected.
(c) if G contains a cycle of length k then H also contain a cycle of length k.
(d) G and H contain same number of vertices and same number of edges.

11. Are the graphs G, K3,3 , Q3 , and C7 in the following figure bipartite? If the graph is bipartite,
find a bipartition; otherwise, explain why it is not bipartite.

6.4
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

12. Let G be a graph with V (G) = {u1 , u2 , . . . , un } and E(G) = {e1 , e2 , . . . , em }, M its incidence
matrix, and A its adjacency matrix. Then
1. What are the row and column sums in M ?
2. If G is simple, what are the row and column sums in A? What other properties does A have?
13. For each pair of simple graphs G and H below, determine whether the graphs are isomorphic
or not. Justify your answer: if you claim that the graphs are isomorphic, give an isomorphism;
if you claim that they are not, give an invariant in which they differ.
a)

b)

c)

6.5
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

(c) degree of corresponding edge;

(d) Degree of vertex.
Next 3 questions refer to A which is Adjacency matrix of a graph G.
 
0 1 1 2 0
 1 0 0 0 1 
 
 1 0 0 1 1 
 
 2 0 1 0 0 
0 1 1 0 0

13. The degree sequence of G is

(a) (2,2,3,3,4)
(b) (0,1,1,2,0)
(c) (0,0,1,1,2)
(d) None of the above.

14. The size of the graph is

(a) 4
(b) 7
(c) 3
(d) None of the above.

15. The entry at position (4,2) in the matrix A2 is

(a) 2
(b) 1
(c) 0
(d) 4

Practical 4C.2: Degree sequence and Dijkstra’s Algorithm

Descriptive Questions 4C.2

1. Check whether the following sequences are graphical or not? For each of those that are graphical,
construct a graph, for which the given sequence is a degree sequence of the graph. If not, Justify
you answer.
(a) 7, 6, 5, 4, 3, 3, 2, 2, 2
(b) 6, 6, 5, 4, 3, 3, 1
(c) 6,3,3,3,3,2,2,2,2,1,1
(d) 6,5,5,4,3,3,3,2,2

6.8
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

(e) 3,3,3,1

2. If a graph G contains a u − v walk of length l, then show that G contains a u − v path of length
at most l.

3. Give examples of non isomorphic graphs that has

(a) same degree sequence.
(b) equal number of vertices and equal number of edges.

4. Find three nonisomorphic graphs with degree sequence 3,3,2,2,2,2.

5. For which integer x(0 ≤ x ≤ 7), if any, the sequence, 7, 6, 5, 4, 3, 2, 1, x graphical?

6. If G is disconnected graph, then show that G is connected.

7. If G is (p, q) graph with minimum degree δ(G) and maximum degree ∆(G), prove that
δ(G) ≤ 2qp
≤ ∆(G).

8. Show that a closed walk of odd length contains a cycle.

n(n−1)
9. Show that the maximum number of edges in a simple graph with n vertices is 2
.

10. A company has branches in each of cities C1 , C2 , . . . , C6 . The fare of direct flight from Ci to
Cj is given by the (i, j)th entry in the following table. (- indicates thee is no flight). Determine
the cheapest route from C1 to other cities using Dijkstra’s Algorithm.

0 50 – 40 25 10
50 0 15 20 – 25
– 15 0 10 20 –
40 20 10 0 10 25
25 – 20 10 0 55
10 25 – 25 55 0

11. Use Dijkstra’s algorithm to find shortest path between the vertices a and z in the following
weighted graphs.

6.9
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

6.10
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

(a) 1
(b) 2
(c) 3
(d) 4

Practical 4C.3: Trees, Cayley Formula

Descriptive Questions 4C.3

1. Show that a vertex v in a tree T is a cut vertex of T if deg(v) > 1.

2. Prove that if T (V, E) is a tree, then the sum of degrees equals 2|V | − 2.

3. Draw all pairwise non-isomorphic trees with |V | = 7 and at least one vertex of degree greater
than or equal to 4.

4. List all pairwise non-isomorphic trees with degree sequence (1,1,1,1,2,2,3,3)

5. Show that there is no tree with degree sequence (1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3).

6. Show that in a tree, if the degree of every non-pendant vertex is 3, then the number of vertices
in the tree is even.

7. A tree has two vertices of degree 2, one vertex of degree 3 and three vertices of degree 4. How
many vertices of degree 1 does it have if it has no vertex with degree greater than 4?

8. Show that vertex v is a cut vertex if and only if there exists two vertices x and y such that v
is on every x − y path in G.

9. Prove that if G is a connected graph of order p ≥ 3 and G has a cut edge then G contains a
cut vertex. Is the converse true? Justify.

10. Show that any two longest paths in a connected graph G has a vertex in common.

11. Show that an edge e of a graph G is a cut edge if and only if there exists two vertices x and y
such that e lies on every x − y path in G.

12. Let τ (G) denote the number of spanning trees of a graph G. Use this τ (G) = τ (G − e) + τ (G.e)
recurrence formula to find τ (K5 ) and τ (K4 − e).

13. Characterize the trees that are complete bipartite graphs.

14. Show that if T is a tree and v, w are non-adjacent vertices of T , then T +{v, w} contains exactly
one cycle.

6.15
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

13. What is the code for p?

(a) 01010
(b) 11110
(c) 10101
(d) 00111

14. What is the code for e?

(a) 101
(b) 100
(c) 001
(d) 110

Practical 4C.4: Applications of Trees

Descriptive Questions 4C.4

1. It’s the weekend and Henry has several ways to spend his Friday and Saturday evenings. He
can study, read watch a television or go out with the boys. Draw a tree which shows all possible
ways Harry can spend his Friday and Saturday evenings.

2. Mary can travel from St. Johns to Corner Brook by car bus or plane and from Corner Brook
to Goose Bay by a plane or boat. Draw a tree showing all possible ways Mary can go from
St.Johns to Goose Bay via Corner Brook. In how many of these ways does she avoid the car or
bus?

3. A coke machine is to identify, by a sequence of tests, the coin that is put into the machine.
Only 8 types of coins are allowed to put in say α, β, χ, δ, φ, γ, η, λ with probabilities 0.15, 0.20,
0.05, 0.19, 0.11, 0.13, 0.17. each test has the effect of partitioning the eight types of coins into
two complementary set and asserting the unknown coin to be in one of the two sets. If the time
taken foe each test is the same, what sequence of tests will minimize the expected time taken
by the coke machine to identify the coin.
n+1
4. Define a binary tree. Show that the number of leaves in a binary tree with n vertices is 2
.

5. Show that a full m−ary tree with i internal vertices contains n = mi + 1 vertices.

6. Show that for a full m−ary tree with

(i) n vertices has i = n−1
m
internal vertices and l = [(m−1)n+1]
m
leaves.
(ii) i internal vertices has n = mi + 1 vertices and l = [(m − 1)i + 1] leaves.
(iii) l leaves has l = (ml−1)
m−1
(l−1)
vertices and i = (m−1) internal vertices.

7. Construct two different Huffman codes for these symbols and frequencies:
t : .11, u : .29, v : .16, e : .14, f : .2, s : .2

6.19
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

8. Construct Huffman codes for the symbols a, l, p, e, d, r, o, c, t, h with the following probabilities
0.04, 0.06, 0.11, 0.09, 0.1, 0.16, 0.14, 0.13, 0.12, 0.05. Using the same encode the message ” apple
help doctor” and also decode the symbol 0110000010110111011100

9. For the given list of symbols and weights,

i) construct a Huffman code using left-to-right ordering to break ties,
ii) calculate its average weighted length,
iii) encode DEFACED and
iv) encode BAGGAGE.

Letter A B C D E F G H
Frequency 0.10 0.15 0.20 0.17 0.13 0.15 0.05 0.05

10. Use Kruskal’s algorithm to find minimum spanning tree for following graphs.

11. The following table gives distances in miles between the cities London, Mexico, Neywork, Paris,
Peking and Tokeyo

L MC NY Pa Pe T
L – 5558 3469 214 5074 5959
MC 5558 – 2090 5725 7753 7035
NY 3469 2090 – 3636 6844 6757
Pa 214 5725 3636 – 5120 6053
Pe 5074 7753 6844 5120 – 1307
T 5959 7035 6757 6053 1307 –

Using Kruskal’s Algorithm determine optimal tree.

12. Use (1) Depth First Search (DFS) and (2) Breath First Search (BFS) algorithm to find a
spanning tree in each of the following graphs

6.20
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

(a) W6 starting at the vertex of degree 6.

(b) K5
(c) K3,4 stating a vertex of degree 3
(d) Q3

13. Describe the trees produced by Breath First Search (BFS) and Depth First Search (DFS)
algorithm for the wheel graph Wn starting at the vertex of degree n where n is integer with
n ≥ 3.

14. Describe the trees produced by Breath First Search (BFS) and Depth First Search (DFS)
algorithm for the complete graph Kn where n is positive integer Justify your answer.

6.21
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

11. Which of the graphs has an Euler circuit?

(a) Graph 3 only
(b) Graph 1 and 3
(c) Graph 2 only
(d) None of these

12. Which of the graphs has an Euler path but no Euler circuit?
(a) Graph 1 only
(b) Graph 3 and 2
(c) Graph 2 only
(d) Graph 3 only

Practical 4C.5: Eulerian Graphs

Descriptive Questions 4C.5

1. Give an example of a graph G such that

(a) both G and G are Eulerian.
(b) G is Eulerian, but G is not.
(c) neither G nor G is Eulerian and both G and G contain an Eulerian trail.
(d) G contains an Eulerian trail and edge e such that G − e is Eulerian.

2. Let G1 and G2 be two Eulerian graphs with no vertex in common. Let G be a graph obtained
by joining some vertex of G1 to some vertex in G2 . Is G Eulerian? Explain.

3. Determine the values of m and n such that Km,n is Eulerian.

6.24
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

4. Prove or disprove
(a) Every Eulerian Bipartite graph has even number of edges.
(b) Every Eulerian simple graph with even number of vertices has an even number of edges.

5. Let G be a connected graph with 2n odd vertices with n ≥ 1. Show that E(G) can be partitioned
into subsets E1 , E2 , . . . En so that < Ei > is an open trail for each i.

6. A power company’s wires in a certain region follow the routes indicated in following figure. The
vertices represent poles and the edges wires. After a severe storm, all the wires and poles must
be inspected. Show that there is a round trip beginning at A, which allows a person to inspect
each wire exactly once. Find such a trip.

7. Use Fleury’s algorithm show that xuywvzwyxuwvxzyx is an optimal tour in the following
weighted graph.

8. Describe an algorithm for solution to Chinese postman problem.

6.25
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

9. Find a solution to the Chinese Postman Problem in the following graph, where every edge has
weight 1.

10. Use Fleury’s algorithm to find an Eulerian circuit for the following graphs.
a)

b)

6.26
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

(c) 3 regular
(d) Not regular

13. Number of edges in Q4 is

(a) 24
(b) 16
(c) 18
(d) 32

14. Number of vertices in Q5 are

(a) 64
(b) 32
(c) 24
(d) 16

Practical 4C.6: Hamiltonian Graphs

Descriptive Questions 4C.6

1. Show that there are n edge disjoint Hamiltonian cycles in K2n+1 . Draw all possible edge disjoint
Hamiltonian cycles inK7 and K9

2. Let G be a graph with p ≥ 3 vertices, then

2
a) Prove that if G has at least p −3p+6
2
edges, then G is Hamiltonian.
p2 −3p+6
b) Find non-Hamiltonian graph with 2
− 1 edges.

3. A mouse eats his way through a 3x3x3 cube of cheese by tunneling through all of the 27x1x1
sub-cubes. If he starts at one corner and always move on to an uneaten sub-cube, can he finish
at the center of the cube?

4. Show that a bipartite graph with odd number of vertices does not have a Hamiltonian cycle.
Hence show that in a chess board of size 5x3 there does not exist a sequence of legal moves by
a knight, starting from some square, visiting each square exactly once and back to the starting
square.

5. Show that any k-regular graph of order (2k − 1) is Hamiltonian.

n!(n−1)!
6. Show that Kn,n is Hamiltonian if and only if n ≥ 2. Hence show that Kn,n has 2
Hamil-
tonian cycles.

7. Does the dodecahedron have a Hamiltonian cycle? Does it satisfy Dirac’s theorem? Justify.

8. Explain why, for any positive integer p the complete bipartite graph Kp,p+3 is not Hamiltonian.

6.29
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

9. What is the minimum number of edges which need to be added to Kp,p+3 to make it into a
Hamiltonian graph? Explain your answer.

10. Show that a Hamiltonian graph cannot contain a bridge.

11. Draw Qn for 1 ≤ n ≤ 4 and write the Hamiltonian cycles in them.

12. Show that Qn is a regular graph on 2n vertices and n2n−1 edges

13. Show that Qn is bipartite

14. Show that the line graph of the star K1,n is the complete graph Kn .

15. Find an expression for the number of edges of L(G) in terms of the degrees of the vertices of G.

16. Show that line graphs L(K3 ) and L(K1,3 ) are isomorphic.

17. Prove that if G is regular of degree k, then L(G) is regular of degree 2k − 2.

18. Find the closure Cl(G) for each of the following graphs? Which of these graphs are Hamiltonian?

6.30
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

Practical 4C.7: Miscellaneous

Unit-I
X
1. If G is a graph of size m, then prove that degv = 2m. Hence prove that every graph has
v∈v(G)
an even number of odd vertices.

2. Let G be a graph of order n. If deg(u) + deg(v) ≥ n − 1 , for every two non adjacent vertices u
and v of G then prove that G is connected.
n−1
3. If G is simple graph on n vertices and δ(G) ≥ 2
, then prove that G is a connected graph
where δ(G) denotes the minimum degree of G.

4. If G is graph of order n with δ(G) ≥ (n − 1)/2, then show that G is connected. Is the bound
(n − 1)/2 sharp? , that is , in this case , can (n − 1)/2 be replaced by(n − 2)/2 ?

5. For any graph G with at least 6 vertices, prove that either G or Gc contains a triangle.

6. State and prove Havel − Hakimi theorem for degree sequence of a graph G.

7. Show that a graph G is disconnected if and only if its vertex set V can be partitioned into two
subsets V1 and V2 such that there exists no edge in G whose one end vertex is in the subset V1
and the other in the subset V2 .

8. Let G be a graph with vertex set V (G) = {v1 , v2 , ....., vn } and adjacency matrix A = [aij ]. Then
(k)
show that the entry aij in ith row and j th column of Ak is the number of distinct vi − vj walks
of length k in G.

9. If (An ) = (anij ) is the nth power of adjacency matrix A of a graph G with

V (G) = {v1 , v2 , . . . vn }, then prove that
i. a2ij , i 6= j is the number of vi − vj path of length 2.
ii. a2ii = deg(vi )
1
iii. 6
trace of A3 is the number of triangles in G.

10. Let A denote the adjacency matrix of a connected graph G with V (G) = {v1 , v2 , . . . vn }, then
show that the distance between vi and vj is the smallest integer n ≥ 0 such that (An )ij 6= 0.

11. If G is simple graph with p vertices, q edges and k components, then prove that q ≥ p − k.

12. Prove that every (p, q) graph with q ≥ p contains a cycle. Is it true if q ≥ p − 1? Justify.

13. Show that a nontrivial graph is bipartite if and only if it contains no odd cycle.

14. Define a self complementary graph.If G is self complementary graph of order p, show that G is
connected and p ≡ 0 or 1( mod 4)

6.31
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

15. Let G be a simple graph and δ(G) ≥ 2, then show that there exists a cycle of length at least
δ(G) + 1 in G.

16. Explain Dijkstra’s algorithm and show that Dijkstra’s algorithm produces the shortest path.

17. Show that every u − v walk W contains u − v path.

Unit-II

1. Let G be a (p, q) graph. Prove that following statements are equivalent.

a) G is tree.
b) G is acyclic and q = p − 1.
c) G is connected and q = p − 1.

2. Show that if a tree has exactly 2 pendant vertices then, all the other vertices have degree 2.

3. Show that there exist a tree with degree sequence d1 ≥ d2 ≥ ..... ≥ dn if and only if 1) di ≥ 1 ,
Xn
for 1 ≤ i ≤ n and 2) di = 2n − 2
i=1

4. Let τ (G) denote the number of spanning trees of a graph G. If e ∈ E(G) is not a loop, then
prove that τ (G) = τ (G − e) + τ (G.e).

5. Show that every nontrivial graph contains at least two vertices which are non-cut vertices.

6. If T is spanning tree of a connected graph G and e is an edge of G that is not in T , then prove
that T + e contains a unique cycle that contains the edge e.

7. If T is tree with n vertices whose degree sequences is d1 , d2 , . . . , dn , then prove that

n
X
di = 2(n − 1)
i=1

8. State and prove Cayley’s formula for spanning trees.

9. State Huffman’s algorithm for prefix code.

10. Show that a graph is connected if and only if it has a spanning tree.

11. Let H be a subgraph of connected graph G, prove that H is subgraph of some spanning tree T
of G if and only if H contains no cycles.

12. Show that every two vertices of a tree are connected by a unique path.

13. Prove that a connected graph G is a tree if and only if every edge of G is a cut edge.

6.32
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

14. Let T be any tree on k + 1 vertices. If δ(G) ≥ k, then show that G contains a tree isomorphic
to T

15. Describe Kruskal’s algorithm for finding minimum spanning tree in a connected weighted graph.

16. Explain Breadth First Search Algorithm.

17. Explain Depth First Search Algorithm.

Unit-III

1. Show that a nontrivial connected graph G is Eulerian if and only if every vertex of G has even
degree.

2. If a connected graph G contains exactly two vertices of odd degree say x and y, then show that
it contains a (x, y)-Eulerian trail.

3. Prove that a connected graph G contains Eulerian trail if and only if exactly two vertices of G
have odd degree. Furthermore, prove that each Eulerian trail of G begins at one of these odd
vertices and ends at the other.

4. Describe Fluery’s Algorithm to find a closed Eulerian trail.

5. If G is a graph on p vertices with p ≥ 3 such that deg(u) + deg(v) ≥ p for every pair of non
adjacent vertices u and v in G, then prove that G is Hamiltonian.

6. If G is graph on p vertices with p ≥ 3 and δ(G) ≥ P2 where δ(G) denotes the minimum degree
of G then show that G contains a Hamiltonian cycle.

7. If u and v are non-adjacent vertices in a graph G such that deg(u) + deg(v) ≥ p. Show that G
is Hamiltonian if and only if G + uv is Hamiltonian

8. If G is Hamiltonian graph then for every nonempty proper subset S of V (G), prove that
ω(G − S) ≤ |S|. Is converse true? Justify.

9. Show that the complete bipartite graph Km,n is Hamiltonian if and only if m = n.

10. If G is a graph on p vertices with p ≥ 3 such that deg(u) + deg(v) ≥ p − 1 for every pair of non
adjacent vertices u and v in G, then show that G contains a Hamiltonian path.

11. If G is a graph on p vertices with p ≥ 3 such that deg(u) + deg(v) ≥ p + 1 for every pair of non
adjacent vertices u and v in G, then show that G contains a Hamiltonian connected.

12. Define closure of a graph C(G) and show that it is well defined.

13. Define closure of a graph C(G) and show that a simple graph is Hamiltonian if and only if its
closure is Hamiltonian.

6.33
US/AMTP5C4 Sem V, Paper 4C: Graph Theory Revised Syllabus 2018

14. Let G be a simple graph with p ≥ 3 . If closure of G is complete, show that G is Hamiltonian.

15. If G is a (p, q) graph with p ≥ 3 and q ≥ 12 (p − 1)(p − 2) + 2, then prove that G is Hamiltonian.

16. Prove that the cube graph Qk is connected bipartite k−regular graph with 2k vertices.

17. Show that the cube graph Qk , k ≥ 2 is a Hamiltonian graph.

18. Show that the line graph a simple graph G is a path if and only if G is a path.

19. Show that if the simple graphs G1 and G2 are isomorphic, then its line graphs L(G1 ) and L(G2 )
are isomorphic. Is converse true? Justify.

6.34