BSc Mathematics SEM V 2017 18 2017-18  Graph Theory Question Paper - Mumbai University | munotes

Questions asked in this paper

• 2) Figures to the right indcate full marks

1. Q1 (a) Attempt any ONE question: 8 marks
   • i. Show that a nontrivial graph is bipartite if and only if it contains no odd cycle
   • ii. If (A”) = is the power of adjacency matrix A of a graph G with V(G) = {v1, v2,.Un}, then prove that
2. Q1 i is the number of v; — v; path of length 2 marks
3. Q3 of is the number of triangles in G
   • (b) Attempt any TWO questions: 12
   • i. Define a complement of a graph G. For any graph G with at least 6 vertices, prove that either G or triangle
   • ii. Explain and write Dijkstra’s algorithm to find the shortest path in a graph G
   • iii. Show that a graph G is disconnected if and only if its vertex set V can be partitioned into two subsets and V2 such that there exists no edge in G whose one end vertex is in the subset and the other in the subset V5
   • iv. Show that the number of edges of a simple graph with n vertices and k components
4. Q2 (a) Attempt any ONE question: 8 marks
   • i. Define a spanning tree of a graph G. Show graph is connected if and only if it has a spanning tree
   • ii. Let G be a (p,q) graph. Prove that following statements are equivalent
   • a) tree
   • b) Gis acyclic and g
   • (b) Attempt any TWO questions: 12
   • i. Show that each label spanning tree with n vertices corresponds to a unique vector
   • ii. Let T be any tree on + 1 vertices. If 6(G) > k, then show that G contains a tree
   • iii. Use Huffman coding to encode these symbols with the given frequencies: a: 0.08, c: 0.12, d: 0.15, e: 0.20, f : 0.35. What is average number of bits required to encode a character?
   • iv. Prove that a connected graph G is a tree if and only if every edge of G is a cut edge
   • Q. P. Code: 19409
5. Q3 (a) Attempt any ONE question: 8 marks
   • i. Prove that a connected graph G contains Eulerian trail if and only if exactly two vertices of G have odd degree
   • ii. If G is a graph on p vertices with p > 3 such that deg(u) + deg(v) > p for every pair of non adjacent vertices u and v in G, then prove that G is Hamiltonian
   • (b) Attempt any TWO questions: 12
   • i. Define a cube graph. Show that the cube graph Q;, k > 2 is a Hamiltonian graph
   • ii. Let G be a connected graph with 2n odd vertices with n > 1. Show that £(G) can be partitioned into subsets so that < E; > is an open trail for each 7
   • iii. If G is Hamiltonian graph then for every nonempty proper subset. S of V(G), prove that w(G—S) < Is converse true? Justify
   • iv. If G is a (p,q) graph with p > 3 and q > — 1)(p — 2) + 2, then prove that G is
6. Q4 Attempt any THREE questions: 15 marks
   • (a) If G is a graph of order p and size q, then prove that = 2q. Hence prove that every graph has an even number of odd vertices
   • (b) If a graph G contains a u—v walk of length then show that G contains a u — v path of length at most l
   • (c) Define minimum spanning tree of a graph. Describe Kruskal’s algorithm for finding mini mum spanning tree in a connected weighted graph
   • (d) Describe the trees produced by Breath First Search (BFS) and Depth First Search (DFS) algorithm for the wheel graph W,, starting at the vertex of degree n where n is integer Let G be asimple graph with p > 8. If closure of G is complete, show that G is Hamiltonian
   • (f) Show that the line graph a simple graph is a path if and only if G is a path

Read from the scan above, so a character or two may differ. The scan is the original.