Tutorial Exercises

1. (a) If G and H are isomorphic graphs, then show that (i) |V (G)| = |V (H)|, (ii) |E(G)| = |E(H)| , (iii) if (f, g)
is an isomorphism between G and H, then show that degG (v) = degH (f (v)), for every v ∈ V (G) and (iv) if
f (u) = v, then f |N (u) is an isomorphism between [NG (u)] and [NH (v)].
(b) Give examples of two non-isomorphic graphs with the same degree sequence.

2. An automorphism of a graph G is an isomorphism f : G → G. If f is an automorphism of a simple graph G, then

show that G − u ≃ G − f (u).
3. Draw all the non-isomorphic simple graphs on n vertices for n = 1, 2, 3, 4.
4. Show that the set of all automorphisms of a simple graph G form a permutation group under the usual binary
operation of functions. Describe the automorphism groups of the following graphs:

G1 G2 G3 G4

5. If H is a subgraph of a simple graph G, does it follow that H c is a subgraph of Gc .

6. A simple graph G on 6 vertices v1 , v2 , v3 , v4 , v5 , v6 has (i) 7 edges in G − v1 and G − v2 , (ii) 6 edges in G − v3 and
G − v4 , (iii) 5 edges in G − v5 and G − v6 . Find the number of edges in G.

7. Draw all the simple graphs G on 6 vertices such that G − u ≃ G − v, for every pair u, v of vertices.
8. A simple graph G on 5 vertices v1 , v2 , v3 , v4 , v5 is such that (i) G − v1 ≃ G − v2 ≃ G − v3 ≃ K2 ∪ K2 , and (ii)
G − v4 ≃ G − v5 ≃ K3 ∪ K1 . Draw G.
9. (a) Verify which of the following sequences are graphic, using (I) Havel-Hakimi Theorem, and using (II) Erdös-
Gallai Theorem.
(i) (5, 5, 5, 2, 2, 2, 1)
(ii) (4, 4, 4, 4, 2, 2, 0)
(b) Whenever a sequence S is graphic (in part (a)), construct a simple graph with S as degree sequence using
Havel-Hakimi Theorem.
10. Give an example of a simple graph that cannot be realized by using the algorithm following Havel-Hakimi criterion.

11. (a) Let G be the graph shown below.

Construct a 3- regular simple graph H such that G ⊑ H.

(b) Show that any simple graph G has a ∆(G)-regular simple supergraph H such that G is an induced subgraph
of H. (If G ⊆ H, then H is called a supergraph of G).
12. Show that any two longest paths in a connected graph have a vertex in common. Does this assertion hold for a
disconnected graph?
13. Let G be a triangle-free graph and let C be a cycle of minimum length in G. Show that every vertex in V (G)−V (C)
is adjacent with at most two vertices of C.
14. Prove or disprove: If G is a connected graph with cut-vertices and if u and v are vertices of G such that d(u, v) =
diam(G), then no block of G contains both u and v.

15. Show that every graph with a cut-vertex has at least two end-blocks. (A block H of G is called an end-block if it
contains exactly one cut-vertex of G.)
16. Draw the following simple graphs:
(a) A graph on 10 vertices with 3 components that has maximum number of edges.
(b) A connected graph (on at most 10 vertices) which has exactly 3 cut-vertices and exactly 2 cut-edges.

17. For any two graphs G1 and G2 , show the following.

(a) k0 (G1 ∪ G2 ) = 0.
(b) k0 (G1 + G2 ) = min{k0 (G1 ) + n(G2 ), k0 (G2 ) + n(G1 )}.
(c) k1 (G1 ∪ G2 ) = 0.
(d) k1 (G1 + G2 ) = δ(G1 + G2 ).
18. Give an example of a graph G with the following properties or state why such examples do not exist.
(a) k0 (G) = 3, k1 (G) = 4 and δ(G) = 5
(b) k0 (G) = 2, k1 (G) = 2 and δ(G) = 4

19. Use Dijkstra’s algorithm to compute a shortest path from the vertex a to every other vertex in the edge weighted
graph shown in Figure 1(a). Show the weighted paths generated at each step of the algorithm.

b 7 d
2
1
d 4 c
a 2 f
1 10
5 6 2
5
c 3 e a 1 b
(a) Qn. No. 19 (b) Qn.No. 20

Figure 1

20. Find the entry in the first row and second column of the matrix generated after applying one iteration of the
Floyd-Warshall algorithm to the weighted graph shown in the Figure 1(b).
21. Let G be a forest with k components. How many edges should one add to G, so that the resulting graph is a tree?
22. Show that in a tree T there are at least ∆(T ) vertices of degree 1.
23. If G is a simple, 3-regular, connected graph, then show that in every spanning tree T of G, n1 (T ) = n3 (T ) + 2,
where ni (T ) = the number of vertices of degree i in T .
24. A tree T on 10 vertices has exactly one vertex of degree 4 and exactly one vertex of degree 3. Find the maximum
degree of T and find all the possible degree sequence of T . Draw three such non-isomorphic trees.
25. The maximum degree of a tree T is 5 and let ni (T ) denote the number of vertices of degree i. If n1 (T ) = 50 and
n2 (T ) = n3 (T ) = n4 (T ) = n5 (T ), find the number of vertices in T .

26. Let G be a graph shown in Figure 2.

6 4

7 3

1 2

Figure 2: G

Draw the following spanning trees of G.

(i) A spanning tree which is a complete binary tree.

(ii) A spanning tree of diameter 5.
(iii) A spanning tree T such that distT (1, v) = distG (1, v), for every vertex v.
27. Prove or disprove: The two trees T1 and T2 with Prüfer codes (1, 2, 1, 2, 1, 2) and (1, 1, 1, 2, 2, 2) respectively are
isomorphic.
28. By using Kruskal’ algorithm compute a minimum weight spanning tree of the graph whose weighted adjacency
matrix is given below. Show the tree generated at every step of the algorithm.

2 6
4
1 c 1
3 2 2
b d
6 e 2 4

29. Find a minimum spanning tree of the weighted graph shown below by using Prim’s algorithm with g as the starting
vertex. Draw all the intermediate trees which lead to M ST . What is the total weight of M ST ?

b 9 c

1 8 2 4
7
f d
a 6
11 10 5 3

g 12 e

30. Draw a simple Eulerian graph G for some n (4 ≤ n ≤ 10) with k0 (G) = 1 and k1 (G) = 4.
31. Draw a simple graph with n = 7, δ(G) ≥ 3 and containing no closed Eulerian trail but containing an open Eulerian
trail.

32. Does there exists a simple Eulerian graph on even number of vertices and odd number of edges? Justify your
answer.