BSc Mathematics SEM V 2018 19 2018-19 Maths 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 from the following: 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. Show that a nontrivial graph is bipartite if and only if it contains no odd cycle
   • (b) Attempt any TWO questions from the following: 12
   • i. Define adjacency matrix of a graph G. If = is the power of adjacency matrix A of a graph G with V(G) = {v1,v2,.Un}, then show that the number of triangles in G is of
   • ii. State Havel — Hakimi theorem for degree sequence of a graph. Check whether the sequence 6, 6, 5, 4,3, 3,1 is graphical or not? If graphical, construct a graph, for which the given sequence is a degree sequence of the graph. If not, Justify you answer
   • iii. Show that a connected (p,q) graph G contains if and only if q > p
   • iv. 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 ?
2. Q2 (a) Attempt any ONE question from the following: 8 marks
   • i. Define a spanning tree of a graph G. Show that a 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
3. Q1 G is tree
4. Q2 Gis acyclic and
5. Q3 Gis connected and
   • (b) Attempt any TWO questions from the following: 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. Define a cut vertex of a graph G. Show that vertex v is a cut vertex if and only if there exists two vertices and y such that v is on every — y path in G
   • 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
6. Q3 (a) Attempt any ONE question from the following: 8 marks
   • i. If G is graph on p vertices with p > 3 and 6(G) > where 6(G) denotes the minimum degree of G, then show that G contains a Hamiltonian cycle
   • ii. Prove that a connected graph G contains Eulerian trail if and 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
   • (b) Attempt any TWO questions from the following: 12
   • i. Define a line graph of a graph. Show that if the simple graphs G and are isomor phic, then its line graphs L(G) and are isomorphic. Is converse true? Justify
   • ii. A mouse eats his way through a 3 x 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?
   • iii. Define closure C(G) of a graph G. Show that a simple graph G is Hamiltonian if and only if its closure is Hamiltonian
   • iv. If G is a graph on vertices with p > 3 such that deg(u) + deg(v) > p—1 for every pair of non adjacent vertices wu and v in G, then show that G contains a Hamiltonian
7. Q4 Attempt any THREE questions from the following: 15 marks
   • (a) Define complement of a graph G. For any graph G with at least 6 vertices, prove that either G or contains a triangle
   • (b) Show that every u—v walk W contains u—v path
   • (c) Explain and write Huffman’s algorithm for prefix code
   • (d) Prove that a connected graph G is a tree if and only if every edge of G is a cut edge
   • (e) If G is Hamiltonian graph then for every nonempty proper subset S of V(G), prove that < Give an example of a graph which satisfies the above condition but not
   • (f) Show that the cube graph Q;, k > 2 is a Hamiltonian graph

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