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



AK 22







Date : 05/05/2008                Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00



Answer ALL the questions.                                                                         (10 x 2 = 20)


  1. Define a graph.
  2. Give an example for the following

(i) Bipartite graph                     (ii) Regular graph

  1. Draw a graph with five vertices and find its complement.
  2. Define a walk and a path.
  3. What is a cut point? Give an example.
  4. Give an example of a graph, which is Eulerian but non-Hamiltonian.
  5. State Fleury’s algorithm.
  6. Define a planar graph and give an example of a non-planar graph.
  7. Define the center of the tree.
  8. Define the chromatic number of a graph.



Answer any FIVE questions.                                                                       (5 x 8 = 40)


  1. (a) Show that every cubic graph has an even number of vertices.

(b) Prove that .

  1. (a) Let G be a k-regular bigraph with bipartition and . Prove that


(b) Prove that any self-complementary graph has 4n or 4n+1 vertices.

  1. (a) In a graph, prove that any u – v walk contains a u – v path.

(b) Show that a closed walk of odd length contains a cycle.

  1. (a) Prove that a graph G with p vertices and  is connected.

(b) If G is not connected then show that  is connected.

  1. Prove that a graph G with at least two points is bipartite if and only if all its cycles are of even length.
  2. Show that the following statements are equivalent for a connected graph G.
  • G is Eulerian.
  • Every vertex of G has even degree.
  • The set of edges of G can be partitioned into cycles.
  1. If G is a graph with p vertices,  and , then prove that G is Hamiltonian.
  2. (a) Prove that  is non-planar.

(b) State and prove Euler’s theorem.




Answer any TWO questions.                                                                       (2 x 20 = 40)


  1. Prove that the maximum number of edges among all p point graphs with no triangles is , where [x] denotes the greatest integer not exceeding the real number x.


  1. Let G be a connected graph with at least three vertices. Prove the following:
  • G is a block if and only if any two vertices of G lie on a common cycle.
  • Any two vertices of G lie on a common cycle if and only if any vertex and any edge of G lie on a common cycle.


  1. Let G be a (p, q) graph. Show that the following statements are equivalent.
  • G is a tree.
  • Every two vertices of G are joined by a unique path.
  • G is connected and p = q + 1.
  • G is acyclic and p = q + 1.


  1. (a) State and prove five colour theorem.

(b) Prove that the following statements are equivalent for any graph G.

  • G is 2-colourable.
  • G is bipartite.
  • Every cycle of G has even length.


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