LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034.

M.Sc. DEGREE EXAMINATION – Mathematics

FourTH SEMESTER – APRIL 2003

MT 4951 / M 1056  –  GRAPH THEORY

 

23.04.2003

1.00 – 4.00                                                                                                     Max : 100 Marks

      Answer ALL questions. Each question carries 25 marks.

 

1. (a) Obtain a necessary and sufficient condition for a sequence (d₁, d_2, …,d_n) to be graphic.

(OR)

(b) Prove that a graph is bipartite if and only if it contains no odd cycle.          (8 marks)

(c) (i) Prove, with usual  notation, that  .

(ii) Find the shortest distance from the vertex u_o  to all other vertices in the following
graph.

 

 

 

 

 

 

(OR)

(d) (i) Prove that a vertex  v of a tree G is a cut vertex of G if and only if d (v)>1.   Deduce
that every nontrivial loopless connected graph has at least two vertices that are not cut
vertices.

(ii)State Cayley’s formula and find the number of distinct spanning trees of the following
graph.                                                                                                (8+9 marks)

 

 

 

2. (a) Define connectivity and edge-connectivity of a graph.   Prove, with usual notation, that
   .

(OR)

• If G is 2-connected, then prove that any two vertices of G lie on a common cycle.

(8 marks)

• (i) Prove that a non empty connected graph is Eulerian if and only if it has no vertex of
  odd degree.

(ii) Obtain Chvatal’s sufficient condition for a simple graph to be Hamiltonian.

(OR)

• (i) Let G be a simple graph and let u and v be non-adjacent vertices in G such that

1. n. Prove that G is Hamiltonian  is Hamiltonian.

(ii) Describe Chinese postman problem. State Fleury’s algorithm. Find an optimal

four in the following graph.

 

 

 

 

 

 

 

 

 

 

 

 

3. (a) Prove that a matching M in G is a maximum matching if and only if G contains no
   M-augmenting path.

(OR)

(b)  Prove , with usual notation, that n if                                      (8 marks)

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

(ii)  Find an optimal matching in the graph given by the following matrix.

 

(OR)

• (i) Define an independent set. Prove with usual notation that n.

(ii) Prove that in a bipartite graph the number of edges in a maximum matching is the
same as the number of vertices in a minimum covering.                          (8+9 marks)

4. (a) State and prove Brook’s theorem.

(OR)

(b)  Let G be a k-critical graph with a 2-vertex cut {u, v}. Prove that  .

(8 marks)

(c)  State and prove kuratowski’s theorem.

(OR)

• (i) Obtain Euler’s formula and deduce that k₅ is non-

(ii)  State and prove the five-colour theorem.                                                (9+8 marks)

 

 

 

Go To Main page