LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

CV 17

B.Sc.  DEGREE EXAMINATION –MATHEMATICS

FIFTH SEMESTER – APRIL 2007

MT 5400 – GRAPH THEORY

 

 

Date & Time: 03/05/2007 / 9:00 – 12:00        Dept. No.                                                     Max. : 100 Marks

 

 

Part A

 

Answer all the questions. Each question carries 2 marks.

 

1. Show that K_p – v = K_{p – 1}.
2. Give an example of a self-complementary graph.
3. Write down the incidence and adjacency matrices of the following graph.

 

 

4. Give an example of a disconnected graph with three components each of which is

3-regular.

5. Give an example of a non-Eulerian graph which is Hamiltonian.
6. For what values of m and n is K_m,n Eulerian?
7. Draw all non-isomorphic trees on 5 vertices.
8. Give an example of a closed walk of even length which does not contain a cycle.
9. Define a planar graph and give an example of a non-planar graph.
10. Define the chromatic number of a graph.

 

Part B

 

Answer any 5 questions. Each question carries 8 marks.

 

11. (a). Prove that in any graph G, the sum of degrees of the vertices is twice the number

of edges. Deduce that the number of vertices of odd degree in any graph is even.

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

12. (a). 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.

(b). Define isomorphism of graphs. If two graphs have the same number of

vertices and same number of edges are they isomorphic? Justify your answer.                                                                                                                           (4+4)

13. (a). Define product and composition of two graphs. Illustrate with examples.

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

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

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

15. (a). Show that if G is disconnected then G^C is connected.

(b). Determine the centre of the following graph.

 

 

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. Let v be a vertex of a connected graph. Then prove that the following statements are equivalent:
    1. v is a cut-vertex of G.
    2. 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.

3. There exist two vertices u and w distinct from v such that v is on every (u, w)-

path.

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

 

Part C

 

Answer any 2 questions. Each question carries 20 marks.

 

19. Prove that the maximum number of edges among all graphs with p vertices with no triangles is [p² / 4], where [x] denotes the greatest integer not exceeding the real number x.                                     (20)
20. (a).Prove that every connected graph has a spanning tree.

(b).Prove that the following statements are equivalent for a connected graph G.

1. G is Eulerian.
2. Every vertex of G has even degree.
3. The set of edges of G can be partitioned into cycles. (5+15)
4. Let G be a (p, q)-graph. Prove that the following statements are equivalent.
5. G is a tree.
6. Any two vertices of G are joined by a unique path.
7. G is connected and p = q + 1.
8. G is acyclic and p = q + 1. (20)

 

22. (a).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.

(b). State and prove the five-colour theorem.                                                 (10+10)

 

Go To Main Page

 

Latest Govt Job & Exam Updates:

View Full List ...