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

FIFTH SEMESTER – APRIL 2008
MT 5400 – GRAPH THEORY
Date : 05/05/2008 Dept. No. Max. : 100 Marks
Time : 9:00 – 12:00
SECTION A
Answer ALL the questions. (10 x 2 = 20)
 Define a graph.
 Give an example for the following
(i) Bipartite graph (ii) Regular graph
 Draw a graph with five vertices and find its complement.
 Define a walk and a path.
 What is a cut point? Give an example.
 Give an example of a graph, which is Eulerian but nonHamiltonian.
 State Fleury’s algorithm.
 Define a planar graph and give an example of a nonplanar graph.
 Define the center of the tree.
 Define the chromatic number of a graph.
SECTION B
Answer any FIVE questions. (5 x 8 = 40)
 (a) Show that every cubic graph has an even number of vertices.
(b) Prove that .
 (a) Let G be a kregular bigraph with bipartition and . Prove that
.
(b) Prove that any selfcomplementary graph has 4n or 4n+1 vertices.
 (a) In a graph, prove that any u – v walk contains a u – v path.
(b) Show that a closed walk of odd length contains a cycle.
 (a) Prove that a graph G with p vertices and is connected.
(b) If G is not connected then show that is connected.
 Prove that a graph G with at least two points is bipartite if and only if all its cycles are of even length.
 Show that the following statements are equivalent for a connected graph G.
 G is Eulerian.
 Every vertex of G has even degree.
 The set of edges of G can be partitioned into cycles.
 If G is a graph with p vertices, and , then prove that G is Hamiltonian.
 (a) Prove that is nonplanar.
(b) State and prove Euler’s theorem.
SECTION C
Answer any TWO questions. (2 x 20 = 40)
 Prove that the maximum number of edges among all p point graphs with no triangles is , where [x] denotes the greatest integer not exceeding the real number x.
 Let G be a connected graph with at least three vertices. Prove the following:
 G is a block if and only if any two vertices of G lie on a common cycle.
 Any two vertices of G lie on a common cycle if and only if any vertex and any edge of G lie on a common cycle.
 Let G be a (p, q) graph. Show that the following statements are equivalent.
 G is a tree.
 Every two vertices of G are joined by a unique path.
 G is connected and p = q + 1.
 G is acyclic and p = q + 1.
 (a) State and prove five colour theorem.
(b) Prove that the following statements are equivalent for any graph G.
 G is 2colourable.
 G is bipartite.
 Every cycle of G has even length.
Latest Govt Job & Exam Updates: