LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

M.Sc. DEGREE EXAMINATION – MATHEMATICS

FOURTH SEMESTER – APRIL 2012

MT 4802 – GRAPH THEORY

 

 

Date : 21-04-2012             Dept. No.                                        Max. : 100 Marks

Time : 1:00 – 4:00

 

 

Answer all the questions. Each question carries 25 marks.

 

1. (a) State Cayley’s formula and determine the number of spanning trees of the following graph.

 

(8)

(OR)

(b) Define a graphic sequence. Obtain a necessary and sufficient condition for a sequence d = (d₁, d₂ … d_n) to be graphic.                                                                         (8)

 

(c) (i) Obtain a characterization for bipartite graphs.

(ii) Prove that an edge of a graph G is a cut edge if and only if it is contained in no cycle of G.                                                                                                 (8 + 9)

(OR)

(d) Determine the shortest path / distance between u₀ and all other vertices of the following graph.

(17)

 

2. (a) Prove with usual notation that . (8)

(OR)

(b) Prove that a simple graph with  is Hamiltonian if and only if its closure is Hamiltonian.                                                                                               (8)

 

(c) (i) If G is a non-Hamiltonian simple graph with n ≥ 3, then prove that G is degree-majorised by some C_{m, n} .

(ii) Prove that a nonempty connected graph is Eulerian if and only if it has no vertex of odd degree.                                                                                        (7 + 10)

(OR)

(d) Describe the Chinese Postman problem. Obtain an optimal tour in the following weighted graph.

(17)

 

3. (a) State and prove Berge theorem on maximum matching. (8)

(OR)

(b) State Kuhn-Munkres algorithm.                                                                            (8)

 

(c) (i) State and prove Hall’s theorem.

(ii) Prove that in a bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum covering.                                 (9 + 8)

(OR)

(d) Prove, with usual notation, that a + b = n = a ¢ + b ¢, if d > 0.                           (17)

 

4. (a) Let G be a k-critical graph with a 2-vertex cut {u, v}. Then prove that G = G₁ G₂ where G_i is a {u, v} – component of type i ( i = 1, 2) and that G₁ + uv is k – critical.                                                                                                                                   (8)

(OR)

(b) Obtain Euler’s formula and deduce that K₅ are non-planar.                                 (8)

 

(c) Prove that a graph is planar if and only if it contains no subdivision of K₅ or K_{3, 3}.

(17)

(OR)

(d) (i) State and prove Brook’s theorem.

(ii) State and prove five color theorem.                                                                (8 + 9)

 

Go To Main page