LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

   B.Sc. DEGREE EXAMINATION – MATHEMATICS

AB 17

FIFTH SEMESTER – November 2008

MT 5408 – GRAPH THEORY

 

 

 

Date : 12-11-08                     Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

PART – A

ANSWER ALL QUESTIONS                                                                          (10 x 2 = 20)

 

1. Define a cubic graph.
2. Prove that .
3. Give an example for an isomorphism between two graphs.
4. Define a self complementary graph and give an example.
5. Define walk and and path.
6. Define an eulerian graph.
7. Prove that every Hamiltonian graph is 2-connected.
8. Define the centre of a tree.
9. If G is k-critical, then prove that .
10. Write the chromatic number for .

 

PART – B

ANSWER ANY FIVE QUESTIONS                                                                 (5 x 8= 40)

11. a) Prove that in any graph G , the number of points of odd degree is even.
12. b) Prove that any self complementary graph has 4n or 4n + 1    (4 + 4)

 

12. a) Let G be a k regular bigraph with bipartition (V₁,V₂) and k>0. Prove that

.

1. b) Prove that a closed walk of odd length contains a cycle.                   (4 + 4)

 

13. Let x be a line of a connected graph G. Then prove that the following are

equivalent

1. x is a bridge of G.
2. ii) There exists a partition of V into subsets U and W such that for each

uU and  wW, the line x is on every  u – w  path.

iii) There exist two points u , w  such that the line x is on every  u –  w path.

 

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

 

• a) Prove that every tree has a centre consisting of either one point or two

adjacent  points.

1. b) Prove that a graph G with p points and is connected.               (4 + 4)

• Prove that every nontrivial connected graph has atleast two points which are not cutpoints.
• If G is a graph with vertices and , then show that G is Hamiltonian.
• State and prove five colour theorem.

 

PART – C

 

 

ANSWER ANY TWO QUESTIONS                                                               (2 x 20 = 40)

 

• a) Prove the maximum number of lines among all p point graphs with no

triangles is .

1. b) Let G₁ be a  graph and G₂ a    Then prove that is

a  graph.                                                                   (15 + 5)

 

• a) Prove that a graph G with at least two points is bipartite if and only if its cycles

are of even length.

1. b) State and prove Chavatal theorem. (10 + 10)

 

• Prove that the following are equivalent for a connected graph G.

1. G is eulerian.
2. Every point of G has even degree.

• The set of edges of G can be partitioned into cycles.

 

• Let G be a tree. Then prove that following are equivalent.

1. i) G is a tree.
2. ii) Every two points of G are joined by a unique path.

iii)   G is connected and  p = q + 1.

1. iv) G is acyclic and  p = q +

 

 

Go To Main Page

 

 

 

 

Latest Govt Job & Exam Updates:

View Full List ...