LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

B.Sc. DEGREE EXAMINATION – MATHEMATICS

 

AB 22

FIFTH SEMESTER – November 2008

MT 5400 – GRAPH THEORY

 

 

 

Date : 12-11-08                     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)

 

1. Show that every cubic graph has an even number of vertices.
2. Let G = (V, E) be a (p, q) graph. Let and . Find the number of vertices and edges in G – v and G – e.
3. Define a walk and a path.
4. What is a connected graph?
5. Give an example of a disconnected graph with 4 components.
6. Draw all non-isomorphic trees on 6 vertices.
7. Define an Eulerian trail and a Hamiltonian cycle.
8. What is a cut edge? Give an example.
9. Determine the chromatic number of K_n.
10. Define a planar graph and give an example of a non-planar graph.

 

 

PART –  B

 

Answer any FIVE questions. Each question carries EIGHT marks.                   (5 x 8 = 40 marks)

 

11. (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)

 

12. Let G₁ be a (p₁, q₁)-graph and G₂ a (p₂, q₂)-graph. Show that G₁ + G₂ is a (p₁ + p₂, q₁ + q₂ + p₁p₂) – graph and G₁ x G₂ is a (p₁ p₂, q₁p₂ + q₂p₁) – graph.

 

13. (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)

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

(b). Find the composition of the following graphs.

 

(4+4)

 

 

 

 

 

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

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

(4+4)

16. Let v be a vertex of a connected graph. Then prove that the following statements are equivalent:
    1. v is a cut-point 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 points u and w distinct from v such that v is on every (u, w)-

path.

 

17. 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.

 

18. State and prove the five-colour theorem.

 

PART – C

 

Answer any TWO questions. Each question carries 20 marks.                            (2 x 20 = 40 marks)

 

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

(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)

 

20. (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)

21. (a). If G is Hamiltonian, prove that for every non-empty 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.

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)

 

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

(20)

 

 

Go To Main page

Latest Govt Job & Exam Updates:

View Full List ...