Ques 1.

i) There exists no 9-vertex graph with three vertices of degree 3, four vertices of degree 2 and two vertices of degree 1.

ii)  has a cycle of length at least 7.

iii) The diameter of a graph cannot exceed its girth.

iv) Every Hamiltonian graph is Eulerian.

v) Every 3-connected graph is 3-edge-connected.

vi) If G is an Eulerian graph, then so is L(G).

vii) .

vii)

.ix) The minimum size of a -chromatic graph is 

x) The 6-dimensional hypercube  has no perfect matching.

Ques 2.

(a) The complement of the Petersen graph is 2-connected. Prove or disprove

(b) Consider a graph G. Let x, y ∈ V (G) be such that x ↔ y. Show that for all z ∈ V (G), |d(x, z) − d(y, z)| ≤ 1

(c) Check whether the following graphs G and H are isomorphic or not

Ques 3.

(a) Let G be a connected n-vertex graph. Prove that G has exactly one cycle iff G has exactly n edges

(b) Find a minimum-weigh spanning tree in the following graph

(c) Prove that every maximal matching of a graph G has at least α 0 (G)/2 edges. 

(d) Find the chromatic and edge-chromatic numbers of the following graph.

Ques 4.

(a) Find the number of spanning trees of the following graph.

(b) Solve the Chinese Postman Problem for the graph given in Q. 3(b). 
(c) Give an example of a 4-critical graph different from a complete graph. Justify the choice of your example.                                                                 (d) State and prove the Handshaking Lemma for planar graphs.

Ques 5.

(a) Verify Euler’s formula for the following plane graph.

(b) Check whether the line graph of C5 × K2 is planar or not. 
(c) What is the minimum possible thickness of a 4-connected triangle-free graph on 8 vertices? Also draw such a graph. 
(d) Define the parameters α(G) and β(G) for a graph G. Also, show that
α(G) + β(G) = n(G).

Ques 6.

(a) What is the maximum possible flow that can pass through the following network? Define such a flow.

(b) State and prove the K¨onig Eg´arvary Theorem. 
(c) Let G be a graph having no isolated vertex and no induced subgraph with exactly two edges. Show that G is a complete graph.

Ques 7.

(a) Find the values of n for which Qn is Eulerian.

(b) Using Fleury’s algorithm, find an Eulerian circuit in the following graph.

(c) The complement of a planar graph is planar. True or false? Justify