LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

B.Sc. DEGREE EXAMINATION – MATHEMATICS

FIFTH SEMESTER – APRIL 2012

MT 5408 – GRAPH THEORY

 

 

Date : 27-04-2012              Dept. No.                                        Max. : 100 Marks

Time : 1:00 – 4:00

 

PART A

Answer ALL the questions                                                                                          (10 x 2 =20)

1. Define a complete bipartite graph.
2. Prove that every cubic graph has an even number of points.
3. If G₁ = K₂ and G₂ = C₃ then find

• G₁G₂ (ii) G₁ + G₂

4. Define distance between any two points of a graph.
5. Define an Eulerian graph and give an example.
6. Prove that every Hamiltonian graph is 2-connected.
7. Draw all possible trees with 6 vertices.
8. Define an eccentricity of a vertex v in a connected graph G.
9. Is K_3,3 planar? If not justify your answer.
10. Find the chromatic number for the following graph.

 

PART B

Answer any FIVE questions                                                                                                    (5 x 8 =40)

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) Prove that                                                                                      (5+3)

12. If Let be a graph and  be a  graph then prove that

(i)  is a  graph.

(ii)  is a  graph.

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

(b) If a graph G is not connected then prove that the graph  is connected.                   (5+3)

14. (a) Prove that a line x of a connected graph G is a bridge if and only if x is not on any cycle of G.

(b) Prove that every non – trivial connected graphs has atleast two points which are not cut points.                                                                                                                              (5+3)

15. If G is a graph with vertices and , then prove that G is Hamiltonian.
16. (a) Prove that every tree has a centre consisting of either one point or two adjacent points.

(b) Let T be a spanning tree of a connected graph. Let x = uv be an edge of G not in T. Then   prove that T + x contains a cycle.                                                                                  (4+4)

17. State and prove Euler’s theorem.
18. Prove that every planar graph is 5-colourable.

 

PART C

Answer any TWO questions                                                                                    (2 x 20 =40)

19. (a) Prove that the maximum number of lines among all p point graphs with no triangles is .

(b) Let  be a  graph then prove that .                                              (15 +5)

20. (a) Prove that a graph G with atleast two points is bipartite if and only if all its cycles are of even length.

(b) Let G be a connected graph with atleast three points then prove that G is a block if and only if any two points of G lie on a common cycle.                                                    (12+8)

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

(i) G is eulerian.

(ii) Every point of G has even degree.

(iii) The set of edges of G can be partitioned into cycles.

 

(b) Show that the Petersen graph is nonhamiltonian.                                                       (12+8)

22. (a) Let be a graph then prove that the following statements are equivalent

(i) G is a tree.

(ii) Every two points of G are joined by a unique path.

(iii) G is connected and .

(iv) G is acyclic and .

 

(b) Prove that every uniquely n – colourable graph is (n – 1) connected.             (14+6)

 

Go To Main Page

 

 

Latest Govt Job & Exam Updates:

View Full List ...