BSc Sem V 2023 2024 Nov 2024 MATHEMATICS ELECTIVE C GRAPH THEORY Question Paper - Mumbai University | munotes

Questions asked in this paper

• 2) Figures to the right indicate full marks

1. Q1 (a) Attempt any ONE question: 8 marks
   • i. Let G be a graph with vertex set V(G) = and adjacency matrix A = Then show that the entry in i” row and j column of A* is the number of distinct v; — v; walks of length in G
   • ii. State and prove Havel — theorem for degree sequence of a graph G
   • (b) Attempt any TWO questions: 12
   • i. Define isomorphism of graphs. Give an example of non isomorphic graphs that has equal number of vertices and equal number of edges. Justify your answer
   • ii. Show that in a party of 6 or more people, either there are 3 persons who know one another or there are three persons who do not know one another
   • iii. If G is simple graph with p vertices, edges and k components, then prove that
2. Q2 (a) Attempt any ONE question: 8 marks
   • i. State and prove Cayley’s formula for spanning trees
   • ii. Define Cut Edge in a simple graph G. Show that an edge e of a graph G is a cut edge if and only if there exists two vertices x and y such that e lies on every x — y path in
   • (b) Attempt any TWO questions: 12
   • i. Show that there exist a tree with degree sequence > >--- if and only if
3. Q1 d; for 1 <i<n and 2) =2n-2
   • ii. Show that every non-trivial graph contains at least two vertices which are non-cut
   • iii. State Huffman’s algorithm for prefix code
4. Q3 (a) Attempt any ONE question: 8 marks
   • i. If a connected graph G contains exactly two vertices of odd degree say x and y, then show that it contains a (x, y)—Eulerian trail
   • 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 closure of a graph C(G) and show that a simple graph is Hamiltonian if and only if its closure is Hamiltonian
   • ii. Prove that the cube graph Q, is bipartite k—regular graph with 2* vertices
   • iii. Describe Fluery’s Algorithm to find a closed Eulerian trail
5. Q4 Attempt any THREE questions: 15 marks
   • (a) Let G be a simple graph and 6(G) > 2, then show that there exists a cycle of length at
   • (b) Explain Dijkstra’s algorithm and show that Dijkstra’s algorithm produces the shortest
   • (c) Show that any two longest paths in a connected graph G has a vertex in common
   • (d) Describe Depth First Search (DFS) algorithm. Use DFS to find spanning tree for the Show that the line graph a simple graph G is a path if and only if G is a path
   • (f) Let G be a connected graph with 2n odd vertices with n > 1. Show that can be partitioned into subsets Eo,. En so that < E; > is an open trail for each 7

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