Tamil Nadu Open University (TNOU) 2009-3rd Year B.Sc Mathematics " GRAPH THEORY " UG 474 BMSA 01 - Question Paper
WS 7
UG-474 BMSA-01B.Sc. DEGREE EXAMINATION JANUARY 2009.
(AY - 2005-06 and CY - 2006 batches only)
Third Year Mathematics GRAPH THEORY Time : 3 hours Maximum marks : 75
SECTION A (5 x 5 = 25 marks)
Answer any FIVE questions.
1. Show that the sum of degrees of the points of a graph G is twice the number of lines.
2. Show that every (p, g)-graph with q > p contains a cycle.
3. Write down the Fleurys algorithm.
4. Let G be a graph with p points and let u and v be a nonadjacent points in G such that d(u) + d(v) > p. Show that G is Hamiltonian if and only if G + uv is Hamiltonian.
5. Prove that every connected graph has a spanning tree.
6. Show that any tree S constructed by Prims algorithm is an optimal tree.
7. Prove that every planner graph G with p > 3 points has at least three points of degree less than 6.
10. Prove that every non trivial graph contains at least two vertices which are not cut vertices.
11. Prove that a connected graph is Eulerian if and only if it has no vertex of odd degree.
12. A (p, q) -graph G is a bipartite graph if and only if it contains no odd cycles.
13. State and prove the Halls theorem.
14. For any graph G prove that i//(G) < A(G) +1.
15. Show that the digraph D is strongly connected if and only if D contains a directed closed walk containing all its vertices.
16. Show that every strong tournament D on p > 3 vertices contains a directed cycle of length k, for every k,
3 <k<p.
3 UG-474
|
Attachment: |
| Earning: Approval pending. |
