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

FIFTH SEMESTER – November 2008
MT 5400 – GRAPH THEORY
Date : 121108 Dept. No. Max. : 100 Marks
Time : 9:00 – 12:00
PART A
Answer ALL the questions. Each question carries 2 marks. (10 x 2 = 20 marks)
 Show that every cubic graph has an even number of vertices.
 Let G = (V, E) be a (p, q) graph. Let and . Find the number of vertices and edges in G – v and G – e.
 Define a walk and a path.
 What is a connected graph?
 Give an example of a disconnected graph with 4 components.
 Draw all nonisomorphic trees on 6 vertices.
 Define an Eulerian trail and a Hamiltonian cycle.
 What is a cut edge? Give an example.
 Determine the chromatic number of K_{n}.
 Define a planar graph and give an example of a nonplanar graph.
PART – B
Answer any FIVE questions. Each question carries EIGHT marks. (5 x 8 = 40 marks)
 (a). Show that in any group of two or more people there are always two with exactly
the same number of friends inside the group.
(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)
 Let G_{1} be a (p_{1}, q_{1})graph and G_{2} a (p_{2}, q_{2})graph. Show that G_{1} + G_{2} is a (p_{1} + p_{2}, q_{1} + q_{2} + p_{1}p_{2}) – graph and G_{1} x G_{2} is a (p_{1} p_{2}, q_{1}p_{2} + q_{2}p_{1}) – graph.
 (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)
 (a). Prove that a closed walk of odd length contains a cycle.
(b). Find the composition of the following graphs.
(4+4)
 (a). Show that if G is disconnected then G^{C} is connected.
(b). Determine the centre of the following graph.
(4+4)
 Let v be a vertex of a connected graph. Then prove that the following statements are equivalent:
 v is a cutpoint of G.
 There exists a partition of V – {v} into subsets U and W such that for each
uU and wW, the point v is on every (u, w) – path.
 There exist two points u and w distinct from v such that v is on every (u, w)
path.
 Let G be a connected plane graph with V, E and F as the sets of vertices, edges and faces respectively. Then prove that  V  –  E  +  F  = 2.
 State and prove the fivecolour theorem.
PART – C
Answer any TWO questions. Each question carries 20 marks. (2 x 20 = 40 marks)
 (a). Prove that the maximum number of edges among all graphs with p vertices with no
triangles is [p^{2 }/ 4], where [x] denotes the greatest integer not exceeding the real number x.
(b). Show that an edge e of a graph G is a cut edge if and only if it is not contained in any cycle
of G. (15+5)
 (a). Prove that a graph G with at least two points is bipartite if and only if all its cycles
are of even length.
(b). Let G be graph with with p ≥ 3 and. Then prove that G is Hamiltonian. (10+10)
 (a). If G is Hamiltonian, prove that for every nonempty proper subset S of V, the
number of components of G \ S , namely, ω(G \ S) ≤  S .
(b). Prove 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. (5+15)
 Let G be a (p, q)graph. Prove that the following statements are equivalent.
 G is a tree.
 Any two vertices of G are joined by a unique path.
 G is connected and p = q + 1.
 G is acyclic and p = q + 1.
(20)