Bhavnagar University 2007 M.Sc Mathematics GRAPH THEORY - Question Paper

M.Sc. (Mathematics) DEGREE EXAMINATION,
DECEMBER 2007.
GRAPH THEORY
Time : 3 hours Maximum : 100 marks
ans any 5 ques..
All ques. carry equal marks.
1. (a) Prove that a graph is bi partite if and only if it contains no odd cycles.
(b) Show that if , then contains a cycle.
(c) Write down the Dijkstra’s algorithm.
2. (a) State and prove Sperner’s lemma.
(b) Prove that an edge of G is a cut edge of if and only if is contained in no cycle of .
(c) Show that every connected graph contains a spanning tree.
3. (a) Prove that .
(b) Show that is m-connected.
4. (a) If is a simple graph and then prove that G is Hamiltonian.
(b) Show that is well described.
5. (a) Prove that .
(b) If , then prove that .
6. (a) State and prove Dirac’s theorem.
(b) If is a connected simple graph and is neither an old cycle nor a complete graph then show that .
7. (a) Show that is non-planar.
(b) If is a connected plane graph then prove that .
(c) Prove that is non-planar.
8. (a) Show that has an orientation such that for all .
(b) Prove that every tournament has a directed Hamilton path.

Earning:   Approval pending.