BSc Mathematics SEM V 2018 19 2018-19 Maths Graph Theory Question Paper - Mumbai University | munotes

Questions asked in this paper

• 2) Figures to the right indicate full marks

1. Q1 Choose correct alternative in each of the following: 20 marks
   • i. The total number of edges in a complete graph on p vertices is
   • ii. If a graph G has 21 edges, 3 vertices of degree 4 and other vertices of degree 3 then the number of vertices in graph G is
   • iii. Which of the following is a correct statement?
   • (a) Isomorphic graphs have same degree sequence;
   • (b) Non isomorphic graphs have different degree sequences;
   • (c) Two graphs are isomorphic if and only if they have same degree sequences;
   • (d) Two isomorphic graphs need not have same degree sequence
   • iv. Value of x, if the degree sequence 8, x; 7, 6, 6, 5, 4, 3, 3, 1, 1, 1 is graphical, is
   • (a) 8or7 (b) 8 (c) 7 (d) None of these
   • v. The number of cut vertices of a tree on n > 3 vertices which is a path is
   • vi. A spanning tree T of a graph G has
   • (a) V(T) = V(G) and E(T) C E(G)
   • (b) and E(T) E(G)
   • (c) V(G)) and E(T)
   • (d) and E(G) C
   • (a) Hamiltonian but not Eulerian (b) Eulerian but not Hamiltonian
   • (c) Both Hamiltonian and Eulerian (d) Neither Hamiltonian nor Hamil
   • viii. Of the following graphs, the non - Hamiltonian graph is
   • (a) Cycle on n vertices (b)
   • (c). Tree on n vertices (d) Cube graph
   • ix. Q, graph with
   • (a) 2” vertices (b) edges
   • (c) Bipartite and Connected (d) All of the above
   • x. If Gis a graph on p vertices and Cl(G) is closure of graph G then closure of G, Cl(G) is
   • (a) Super graph of G (b) subgraph of G
   • (c) compliment of G (d) None of these
2. Q2 (a) Attempt any ONE question from the following: 8 marks
   • i. Show that a nontrivial graph G is bipartite if and only if it contains no odd cycle
   • ii. State and prove Havel — Hakimi theorem for degree sequence of a graph G
   • (b) Attempt any TWO questions from the following: 12
   • i. Define Adjacency matrix A of a graph G. Let G be a graph with vertex set V(G) = V2, and adjacency matrix A = Show that the entry in i” row and column of is the number of distinct v; — v; walks of length k in G
   • ii. Let G be a simple graph and 6(G) > 2, then show that there exists a cycle of length at least 6(G) +1 in G
   • iii. If G is simple graph on p vertices and 6(G) > then prove that G is a connected graph where 6(G) denotes the minimum degree of G
   • iv. Show that Dijkstra’s algorithm produces the shortest path
3. Q3 (a) Attempt any ONE question from the following: 8 marks
   • i. State and prove Cayley’s formula for spanning trees
   • ii. Define a spanning tree of a graph G. Show graph connected if and only if it has a spanning tree
   • (b) Attempt any TWO questions from the following: 12
   • i. Define a cut vertex of a graph G. Show that every nontrivial graph contains at least two vertices which are non-cut vertices
   • ii. 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
   • iii. Let denote the number of spanning trees of a graph G. If e E(G) is not a loop, then prove that 7(G) = — e)
   • iv. Use Huffman coding to encode these symbols with the given frequencies: b: 0.10, 0.15, e: 0.30. What is average number of bits required to encode a character?
4. Q4 (a) Attempt any ONE question from the following: 8 marks
   • i. If wand v are non-adjacent vertices in a graph G such that deg(u) +deg(v) > p. Show is Hamiltonian if and only if G+ uv is Hamiltonian
   • ii. Prove 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 cube graph Q; Show that the cube graph k.> 2 is a Hamiltonian graph
   • ii. If G is a graph on p vertices with p > 3 such that deg(u) + deg(v) > p—1 for every pair of non adjacent vertices u and v in G, then show that G contains a Hamiltonian
   • iii. 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?
   • iv. If G is Hamiltonian graph then for every nonempty proper subset S of V(G), prove that w(G—S) < |S|. Give an example of a graph which satisfies the above condition but not Hamiltonian
5. Q5 Attempt any FOUR questions from the following: 20 marks
   • (a) If G is simple graph with p vertices, q edges and k components, then prove that > p—k
   • (b) If G(p,q) is a graph with p vertices and q edges, then prove that = 2q. Hence prove that every graph has an even number of odd vertices
   • (c) Describe Kruskal’s algorithm for finding minimum spanning tree in a connected weighted
   • (d) 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
   • (e) Define closure of a graph C(G) and show that graph is Hamiltonian if and only if its closure is Hamiltonian
   • (f) Define a line graph of a graph G. Show that the line graph a simple graph G is a path if and only if path

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