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




AB 22


FIFTH SEMESTER – November 2008





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

Time : 9:00 – 12:00



Answer ALL the questions. Each question carries 2 marks.                                (10 x 2 = 20 marks)


  1. Show that every cubic graph has an even number of vertices.
  2. Let G = (V, E) be a (p, q) graph. Let and . Find the number of vertices and edges in Gv and Ge.
  3. Define a walk and a path.
  4. What is a connected graph?
  5. Give an example of a disconnected graph with 4 components.
  6. Draw all non-isomorphic trees on 6 vertices.
  7. Define an Eulerian trail and a Hamiltonian cycle.
  8. What is a cut edge? Give an example.
  9. Determine the chromatic number of Kn.
  10. Define a planar graph and give an example of a non-planar graph.





Answer any FIVE questions. Each question carries EIGHT marks.                   (5 x 8 = 40 marks)


  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). Let G be a (p, q)-graph all of whose vertices have degree k or k + 1. If G has t

vertices of degree k then show that t = p(k+1)-2q.                                                           (4+4)


  1. Let G1 be a (p1, q1)-graph and G2 a (p2, q2)-graph. Show that G1 + G2 is a (p1 + p2, q1 + q2 + p1p2) – graph and G1 x G2 is a (p1 p2, q1p2 + q2p1) – graph.


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

(b).Prove that a graph with p vertices and  is connected.                                       (4+4)

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

(b). Find the composition of the following graphs.








  1. (a). Show that if G is disconnected then GC is connected.

(b). Determine the centre of the following graph.


  1. Let v be a vertex of a connected graph. Then prove that the following statements are equivalent:
    1. v is a cut-point of G.
    2. There exists a partition of V – {v} into subsets U and W such that for each

uU and  wW, the point v is on every (u, w) – path.

  1. There exist two points u and w distinct from v such that v is on every (u, w)-



  1. Let G be a connected plane graph with V, E and F as the sets of vertices, edges and faces respectively. Then prove that | V | – | E | + | F | = 2.


  1. State and prove the five-colour theorem.




Answer any TWO questions. Each question carries 20 marks.                            (2 x 20 = 40 marks)


  1. (a). Prove that the maximum number of edges among all graphs with p vertices with no

triangles is [p2 / 4], where [x] denotes the greatest integer not exceeding the real number x.

(b). Show that an edge e of a graph G is a cut edge if and only if it is not contained in any cycle

of G.                                                                                                                                (15+5)


  1. (a). Prove that a graph G with at least two points is bipartite if and only if all its cycles

are of even length.

(b). Let G be graph with with p ≥ 3 and. Then prove that G is Hamiltonian.                      (10+10)

  1. (a). If G is Hamiltonian, prove that for every non-empty proper subset S of V, the

number of components of G \ S , namely, ω(G \ S) ≤ | S |.


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

  1. G is Eulerian.
  2. Every vertex of G has even degree.
  3. The set of edges of G can be partitioned into cycles.                        (5+15)


  1. Let G be a (p, q)-graph. Prove that the following statements are equivalent.
  2. G is a tree.
  3. Any two vertices of G are joined by a unique path.
  4. G is connected and p = q + 1.
  5. G is acyclic and p = q + 1.



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