B.TECH - Semester 8 graph theory Question Paper 2021 (feb)
Practice authentic previous year university questions for better exam preparation.
Sample Questions
- In any graph G, show that the number of vertices with odd degree is even.
- Show that a connected graph with $n$ vertices and $n-1$ edges is a tree.
- Prove that any two simple connected graphs with $n$ vertices, all of degree two, are isomorphic.
- Prove that every connected graph has at least one spanning tree.
- What are the difficulties encountered in the theory of sequential machine? $$ \text { ( } 5 \times 4=20 \text { Marks) } $$ PART - B Answer any one questions from each Module. Each question carries 20 marks Module - I
- Prove the following theorems (a) The total number of different, not edge disjoint, Hamiltonian circuits in a complete graph of n vertices is $(n-1)!/ 2$.
- Prove the following theorems (b) A connected graph G is a Euler graph if and only if it can be decomposed into circuits.
- Prove the following theorems (c) Prove that in any tree, there are atleast two pendant vertices. OR
- (a) In a complete graph having odd number of vertices, how many edge disjoint Hamiltonian circuits exist? Explain.
- (b) Show a tree in which its diameter is not equal to twice the radius. Under what condition does this inequality hold? Elaborate.
- (a) Explain Euler digraph along with its properties.
- (b) Discuss about some types of digraph with suitable examples.
- (a) How binary relations are closely related to theory of graphs? Explain in detail.
- (b) Find the number of vertices, edges and regions for the following planar graph and verify that Euler's Theorem for connected planar graphs is satisfied.
- (a) Write an algorithm to find a Hamiltonian path in a given undirected graph. 10
- (b) How do you determine whether or not the two graph G1 and G2 are isomorphic? Explain with example. OR 2 11．（a）How do you generate the fundamental circuits in a given graph？illustrate the procedure with a suitable example． （b）Illustrate DFS algo...