Loyola College B.Sc. Mathematics Nov 2008 Graph Theory Question Paper PDF Download

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)

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

 

  1. a) Let G be a k regular bigraph with bipartition (V1,V2) and k>0. Prove that

.

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

 

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

 

  1. 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 G1 be a  graph and G2 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 ...

© Copyright Entrance India - Engineering and Medical Entrance Exams in India | Website Maintained by Firewall Firm - IT Monteur