Exercise 6.1
Show that the following 3 drawings (of the Petersen graph) are isomorphic.
6 η ι
Exercise 6.2
(i) Sketch all non-isomorphic simple graphs with 3 vertices.
(ii) Sketch all 11 non-isomorphic simple graphs with 4 vertices and identify all pairs of complement graphs (including self-complementary ones, i.e., one that is isomorphic to its own complement).
Exercise 6.3
Show that two simple graphs are isomorphic iff their complement graphs are isomorphic.
Exercise 6.4
How many cycles of length n are there in the complete graph Kn, n ≥ 1?
Exercise 6.5
Consider the complete graph Kn, n > 0. Show that if Pi ni = n, ni ∈ N, then .
Exercise 6.6
Given a finite graph G with the degrees of every vertex at least 2, show that G contains a cycle (as a subgraph).
Exercise 6.7
A graph G is called k-regular if all vertices of G have the same degree k.
(i) Show that a k-regular bipartite graph has no cut-edge for k ≥ 2.
(ii) Show that a k-regular bipartite graph has a perfect matching for k ≥ 1.
(iii) Show that every k-regular bipartite graph has a perfect matching for k ≥ 1.
Exercise 6.8
Given graph G, show that G is a tree iff G is connected and e is a cut-edge for all e ∈ E(G).
Exercise 6.9
Given a finite matroid M = (E,I), Show that if A,B are bases of M and a ∈ A−B, then there exists b ∈ B −A such that (A − a) ∪ b is also a basis.
Exercise 6.10
Given a set E with |E| = n, n ∈ N, Let I = {F ⊂ E | |F| ≤ k}, 0 ≤ k ≤ n. Show that (E,I) is a matroid.
Exercise 6.11
Sketch all 8 spanning trees of the following graph.[1]
Exercise 6.12
Given the following simple connected graph, with weighted edges specified as follows,
(i) Find a minimum-weight spanning tree via Kruskal’s algorithm. List the edges chosen in order and sketch the tree.
(ii) Given the root vertex a, find a shortest-path spanning tree via Dijkstra’s algorithm. List the edges chosen in order, list the shortest path distance (from root vertex) to each vertex. Sketch the tree.
Page 2 of 2
[1] For counting the number of spanning trees, check Kirchhoff’s matrix tree theorem.
Page 1 of 2
