Loyola College M.Sc. Mathematics April 2012 Graph Theory Question Paper PDF Download

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 = (d1, d2dn) 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 u0 and all other vertices of the following graph.

(17)

 

  1. (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 Cm, 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)

 

  1. (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)

 

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

(OR)

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

 

(c) Prove that a graph is planar if and only if it contains no subdivision of K5 or K3, 3.

(17)

(OR)

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

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

 

Go To Main page

 

 

 

© Copyright Entrance India - Engineering and Medical Entrance Exams in India | Website Maintained by Firewall Firm - IT Monteur