BSc Mathematics SEM V 2019 20 Oct 2019-20 MATHS MATHEMATICS GRAPH THEORY 15.10.19 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 smallest n such that the complete graph K,, has atleast 600 edges
   • ii. Every vertex induced subgraph of a complete graph
   • (a) is complete (b) bipartite
   • (c) disconnected (d) acyclic
   • iii. Which one of the following sequences is graphic?
   • iv. If A(G) is adjacency matrix of graph G then number of 1’s in each row or column denotes
   • (a) Number of edges in graph G
   • (b) Degree of corresponding vertex
   • (c) Degree of the corresponding vertex
   • (d) None of the above
   • v. If there is a tree with 3 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree 4 then the number of pendent. vertices in tree is
   • vi. The number of different labeled trees of order 15 is:
   • (c) (d) None of the above
   • vii. How many edges does a full binary tree with 1000 internal vertices have? A connected graph has Eulerian trail if it has
   • (a) At most two vertices of odd degree
   • (b) Exactly two vertices of odd degree
   • (c) At least two vertices of odd degree
   • (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 is
2. Q2 (a) Attempt any ONE question from the following: 8 marks
   • i. If (A") = is the n 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) gtrace of is the number of triangles in G
   • ii. Define a self complementary graph. If G is self complementary graph of order p, show that G is connected and or mod 4)
   • (b) Attempt any TWO questions from the following: 12
   • i. State Havel — Hakimi theorem for degree sequence of a graph. Check whether the sequence 5, 4,3,3,2,2,2,1,1,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
   • ii. Show that the number of edges of a simple graph with p vertices and k components
   • iii. 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
   • iv. Prove that every (p,q) graph with > p contains a cycle. Is it true if >
3. Q3 (a) Attempt any ONE question from the following: 8 marks
   • i. Define a spanning tree of a graph G. Show that a graph G is connected if and only if it has a spanning tree
   • ii. State and prove Cayley’s formula for spanning trees
   • (b) TWO questions from the following: 12
   • i. 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 vis on every — y path in G
   • ii. Let denote the number of spanning trees of a graph G. If e E(G) is not a loop, then prove that 7(G) =
   • iii. Explain and write Huffman’s algorithm for prefix code
   • iv. Let T be any tree on. k + vertices. If 6(G) > k, then show that G contains a tree
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 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
   • (b) Attempt any TWO questions from the following: 12
   • i. Define closure of a graph C(G) and show that it is well defined
   • ii. If G is a (p,q) graph with p > 3 and > 3(p — + 2, then prove that G is
   • iii. Prove that the cube graph Q, is bipartite k—regular graph with vertices
   • iv. Let G, and G2 be two Eulerian graphs with no vertex in common. Let G be a graph obtained by joining some vertex of G to some vertex in Is G Explain
5. Q5 Attempt any FOUR questions from the following: 20 marks
   • (a) Define isomorphism of graphs. Give examples of non isomorphic graphs that has
   • (ii) equal number of vertices and equal number of edges
   • (b) 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
   • (c) Describe the trees produced by Breath First Search (BFS) and Depth First Search (DFS) algorithm for the complete graph where n is positive integer Justify your answer
   • (d) Prove that if G is a connected graph of order p and G has a cut edge then G contains a cut vertex. Is the converse true? Justify (ec) Prove that if G is regular of degree k, then L(G) is regular of degree 2k — 2
   • (f) Draw Q, for and write the Hamiltonian cycles in them

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