BSc Mathematics SEM V ATKT May 2018-19 ATKT MATHEMATICS 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. Which of the following statement is true?
   • (a) In a simple graph there are at most two vertices of equal degree
   • (b) In a simple graph there at least two vertices of equal degree
   • (c) Degree of vertices are all distinct
   • (d) None of these
   • ii. The number of edges of Complete Bipartite graph is
   • (a) m+n (b) mn +n? (d) None of these
   • iii. Adjacency matrix of a simple graph is
   • (a) Binary and symmetric (b) Only (c) Only Symmetric (d) None of these
   • iv. Let G be a graph on 8 vertices that has no pair of adjacent edges. The degree sequence of
   • (c) (d) such a graph does not exist
   • v. A 1) graph is a tree if
   • (a) G is connected (b) Gis acyclic
   • (c) Must be (a) or (b) (d) None of the above
   • vi. Let T be a tree with n vertices, where n > 4 and let v be a vertex of maximum degree in T, then T is a path if d(v) is
   • vii. is a cut vertex of a graph G, then
   • (a) Gis Hamiltonian and Eulerian. (b) G is Hamiltonian but not Eulerian
   • (c) G is not. Hamiltonian, (d) None of the above
   • viii. Complete bipartite graph is Eulerian if
   • (a) [Vil = (b) [Vil >
   • (c) = = Even Number (d) None of these
   • ix. If Gis Hamiltonian and if S is any non empty proper subset of V(G) then
   • (c) > |S| (d) None of these
   • x. Number of edges in cube graph Q, is
2. Q2 (a) Attempt any ONE question from the following: 8 marks
   • i. State and prove Havel — Hakimi theorem for degree sequence of a graph G
   • ii. If (A”) = is the power of adjacency matrix A of a graph G with V(G) = {v1, then prove that
   • (a) is the number of v; — v; path of length 2
   • (c) of A? is the number of triangles in
   • (b) Attempt any TWO questions from the following: 12
   • i. State and prove Hand-Shaking theorem for Graph. Hence prove that every graph has an even number of odd vertices
   • ii. For any graph G with at least 6 vertices, prove that either G or contains a triangle
   • iii. If G is simple graph with p vertices, q edges and k components, then prove that
   • iv. If G is graph of order p with 6(G) > (p— 1)/2, then show that G is connected. Is the bound sharp?, that is , in this case ; can be replaced by(p —
3. Q3 (a) Attempt any ONE question from the following: 8 marks
   • i. Let G be a (p,q) graph. Prove that following statements are equivalent
   • a) G is tree
   • b) G is acyclic and
   • c) G is connected and q = p—1
   • ii. State and prove Cayley’s formula for spanning trees
   • (b) Attempt any TWO questions from the following: 12
   • i. Show that there tree with degree sequence d; > > . > if and only if a)
   • ii. Define a cut vertex of a graph G. Show that vertex v is a cut vertex if and only if there exists two vertices x and y such that v is on every — y path in G
   • iii. Explain and write Huffman’s algorithm for prefix code
   • iv. Write Breadth First Search and Depth First Search Algorithm for finding a spanning
4. Q4 (a) Attempt any ONE question from the following: 8 marks
   • i. Show that a nontrivial connected graph G is Eulerian if and only if every vertex of G has even degree
   • ii. If Gis graph vertices with p > 3 and 6(G) > 4 where denotes the minimum degree of G then show that G contains a Hamiltonian cycle
   • (b) Attempt any TWO questions from the following: 12
   • i. Define a line graph L(G) of a graph G. Show that if the simple graphs and G2 are isomorphic, then its line graphs and L(G2) are isomorphic. Is converse true?
   • ii. Let G be a simple graph with p > 3. If closure of G is complete, show that G is
   • iii. Prove that the cube graph Q, is bipartite k—regular graph with 2* vertices
   • iv. If G is a (p,q) graph with p > 3 and > — 2) + 2, then prove that G is
5. Q5 Attempt any FOUR questions from the following: 20 marks
   • (a) 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
   • (b) Show that every walk W contains u—v path
   • (c) Prove that a connected graph a tree if and only if every edge of G cut edge
   • (d) Show that every two vertices of a tree are connected by a unique path
   • (e) If G is Hamiltonian graph then for every nonempty proper subset S of V(G), prove that w(G—S) Is converse true? Justify
   • (f) Describe Fluery’s Algorithm to find a closed Eulerian trail

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