BSc IT Sem VI 2014 2015 2015 TYIT Sem Vl C++ Question Paper - Mumbai University | munotes

Questions asked in this paper

• (4) Figures to the right indicate marks. L

1. Q2 (@) State and prove Cayley’s spanning trees. 8 marks
   • (ii) Let,G be (p, q) graph. Show the following statements are Define a binary that the number of leaves in a binary (6) 4 (ii) Prove is a nontrivial tree then there exists at least 2 vertices are pendant vertices 8
   • (iii) IfT with n vertices whose degree that a graph is connected if and only if it has a spanning tree. (6) 6
2. Q3 Show that the cube graph is connected bipartite k-regular
   • (ii) graph on p vertices with p2 3 such that deg(u)tdeg(v)=p every pair of non adjacent vertices u and v in G , then prove that G is Hamiltonian. ‘ @ Define closure of a graph C(G) and show that if the closure of (6) graph Gis complete tices and q edges with p= 3 (6) prove that G is Ham (6) Show that there are D edge disjoin Sho . Hamiltonian cycles in Also draw all edge (6) 8
   • iv) graph on p vertices how that G pair of non adjacent vertices U andvinG, then sho
   • (i) Let A denote the adjacency matrix of a connected graph G with & V(G) then show that the distance between v, is the smallest integer = 0 such that (A”), #0 x Show that a vertex v is a cut vertex if and only if there exists (5) x and y such that v is on every x y path in G Let denote the number of spanning trees of a graph (5) is not a loop then prove that = t(G — e) +
   • (iv) Prove that vertex connectivity of a graph is less than @equal to Hamiltonian graph then for every subsetS of V(G), prove that
   • (vi) Prove that the cube graph Q,, with n> 2 graph

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