BSc Mathematics SEM V 2016 17 2016-17 Maths 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. Define a self complementary graph. If G is self complementary graph of order p, show that G is connected and or 1( mod 4)
   • ii. State and prove Havel — Hakimi theorem for degree sequence of a graph G
   • (b) Attempt any TWO questions: 12
   • i. Define adjacency matrix of a graph G. If (A") = is the power of adjacency matrix A of a graph G with V(G) = then show that the number of triangles in G is Ztrace of
   • ii. If G is graph of order n with 6(G) > (n — 1)/2, then show that G is connected. Is the bound (n — 1)/2 sharp?, that is, in this case, can (n — 1)/2 be replaced by(n — 2)/2 ?
   • iii. Show that every walk W contains v path
   • iv. If G and H are isomorphic graphs, then show that the degree sequence of the vertices of G are the same as the degree sequence of the vertices of H
2. Q2 (a) Attempt any ONE question: 8 marks
   • i. Let G be a (p,q) graph. Prove that following statements are equivalent
3. Q1 G is tree
4. Q2 Gis acyclic and 1
5. Q3 Gis connected. and = p—1
   • ii. Define a spanning tree of a graph G. Show graph is connected if and only if it has a spanning tree
   • (b) Attempt any TWO questions: 12
   • i. Show that each label spanning tree with n vertices corresponds to a unique vector
   • ii. denote the number of spanning trees of a graph G. If e E(G) is not a loop,
   • iii. If T is spanning tree of a connected graph G and e is an edge of G that is not in T, then prove that. 7’+ e contains a unique cycle that contains the edge e
   • iv. Describe the trees produced by Breath First Search (BFS) and Depth First Search (DFS) algorithm for the complete graph K,, where n is positive integer. Justify your
   • Q.P.Code : 07078
6. Q3 (a) Attempt any ONE question: 8 marks
   • i. Prove that a connected graph G contains Eulerian trail only if exactly two vertices of G have odd degree. Furthermore, prove that each Eulerian trail of G begins at one of these odd vertices and ends at the other
   • ii. If u and v are non-adjacent vertices in a graph G such that deg(u) + deg(v) > p, then show that G is Hamiltonian if and only if G+ uv is Hamiltonian
   • (b) Attempt any TWO questions: 12
   • i. Define closure C(G) of a graph G. 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 vertices
   • iii. If G is Hamiltonian graph then for every nonempty proper subset S of V(G), prove that w(G— < |S|. Give an example of a graph which satisfies the above condition but not Hamiltonian
   • iv. A mouse eats his way through a 3 3.x 3 cube of cheese by tunneling through all of the 27 x 1 x 1 sub-cubes. If he starts at one corner and always move on to.an uneaten sub-cube, can he finish at the centre of the cube?
7. Q4 Attempt any THREE questions: 15 marks
   • (a) Prove that every (p,q) graph with q > p contains a cycle. Is it true if >p—1? Justify
   • (b) Explain Dijkstra’s algorithm to find shortest path in a graph G
   • (c) Prove that if G is a connected graph of order p > 3 and G has a cut edge then G contains a cut vertex. Is the converse true? Justify
   • (d) Describe Kruskal’s algorithm for finding minimum spanning tree in a connected weighted
   • (e) Define a line graph of a graph G. Show that. the line graph a simple graph G is a path if and only if Gis a path
   • (f) Show that complete bipartite graph is Hamiltonian

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