Loyola College B.Sc. Mathematics April 2012 Graph Theory Question Paper PDF Download

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 G1 = K2 and G2 = C3 then find
  • G1G2 (ii) G1 + G2
  1. Define distance between any two points of a graph.
  2. Define an Eulerian graph and give an example.
  3. Prove that every Hamiltonian graph is 2-connected.
  4. Draw all possible trees with 6 vertices.
  5. Define an eccentricity of a vertex v in a connected graph G.
  6. Is K3,3 planar? If not justify your answer.
  7. Find the chromatic number for the following graph.

 

PART B

Answer any FIVE questions                                                                                                    (5 x 8 =40)

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

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

(i)  is a  graph.

(ii)  is a  graph.

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

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

  1. If G is a graph with vertices and , then prove that G is Hamiltonian.
  2. (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)

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

 

PART C

Answer any TWO questions                                                                                    (2 x 20 =40)

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

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

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

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

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