LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034  B.Sc. DEGREE EXAMINATION – MATHEMATICS

AA 08

FIFTH SEMESTER – NOV 2006

         MT 5400 – GRAPH THEORY

(Also equivalent to MAT 400)

 

 

Date & Time : 03-11-2006/9.00-12.00         Dept. No.                                                       Max. : 100 Marks

 

 

Part A

 

Answer all the questions. Each question carries 2 marks.

 

1. Give an example of a regular graph of degree 0.
2. The only regular graph of degree 1 is K₂. True or false? Justify your answer.
3. What is a self-complementary graph?
4. What is the maximum degree of any vertex in a graph on 20 vertices?
5. Show that the two graphs given below are not isomorphic.

 

 

 

6. Give an example of a closed walk of even length which does not contain a cycle.
7. Draw all non-isomorphic trees on 6 vertices.
8. Give an example of a graph which has a cut vertex but does not have a cut edge.
9. Define a block.
10. Give an example of a bipartite graph which is non-planar.

 

Part B

Answer any 5 questions. Each question carries 8 marks.

 

11. (a). Prove that in any graph,

(b). Draw the eleven non-isomorphic sub graphs on 4 vertices.                     (4+4)

12. (a). Define the incidence and adjacency matrices of a graph. Write down the

adjacency matrix of the following graph:

(b). Let G be a (p, q)-graph all of whose vertices have degree k or k + 1. If G

has t vertices of degree k then show that t = p(k+1)-2q.                                                                                                                                       (4 + 4)

13. Prove that the maximum number of edges among all graphs with p vertices, where p is odd, with no triangles is [p² / 4], where [x] denotes the greatest integer not exceeding the real number x.
14. (a). Let G be a k-regular bipartite graph with bipartition (X, Y) and k > 0. Prove

that

(b). Show that if G is disconnected then G^C is connected.                (4 + 4)

 

15. (a). Prove that any self – complementary graph has 4n or 4n+1 vertices.

(b).Prove that a graph with p vertices and  is connected.   (4 + 4)

 

16. Prove that a graph G with at least two points is bipartite if and only if all its cycles are of even length.

 

17. (a). Prove that a closed walk of odd length contains a cycle.

(b). Prove that every tree has a centre consisting of either one vertex or two

adjacent vertices.

18. Let G be graph with with p ≥ 3 and, then prove that G is Hamiltonian.

 

Part C

 

Answer any 2 questions. Each question carries 20 marks.

 

19. Let G₁ be a (p₁, q₁)-graph and G₂ a (p₂, q₂)-graph. Show that
20. G₁ x G₂ is a (p₁ p₂, q₁p₂ + q₂p₁)-graph and
21. G₁[G₂ ] is a (p₁ p₂, q₁p₂² + q₂p₁)-graph.

 

20. Prove that the following statements are equivalent for a connected graph G.
21. G is Eulerian.
22. Every vertex of G has even degree.
23. The set of edges of G can be partitioned into cycles.

 

21. Let G be a (p, q)-graph. Prove that the following statements are equivalent.
22. G is a tree.
23. Any two vertices of G are joined by a unique path.
24. G is connected and p = q + 1.
25. G is acyclic and p = q + 1.

 

22. (a). Obtain Euler’s formula relating the number of vertices, edges and faces of

a plane graph.

 

(b). Prove that every planar graph is 5-colourable.                             (10+10)

 

Go To Main Page

 

Latest Govt Job & Exam Updates:

View Full List ...