BSc Mathematics SEM V 2016 17 2016-17 Graph Theory And Combinatorics (Old) Question Paper - Mumbai University | munotes

Questions asked in this paper

• 2) Figures to the right indcate full marks

1. Q1 (a) Attempt any ONE question: i, If (A") = is the n power of adjacency matrix A of a graph G with V(G) = then prove that 8 marks
   • (1). #7 is the number of v; — v; path of length 2
   • (2) al, =
   • (3) of A? is the number of triangles in G
   • ii. State and prove Havel — Hakimi theorem for degree sequence of a graph
   • (b) Attempt any TWO questions: 12
   • i. Define cut edge.of a graph G. Prove that an edge e of a graph G is a cut edge of G if and only if e is acyclic and hence prove that every edge in a tree is a cut edge
   • ii. If G is a simple graph on at least six vertices, then prove that either
   • iii. If G is graph of order n with > (n — 1)/2, then show that G is connected where 6(G) denotes the minimum degree of G. Give an example of a graph with 6(G) > (n — 2)/2 which is not connected
   • iv. Prove that every (p,q) graph with g > p contains a cycle. Is it true if >
   • (a) Attempt any ONE question: 8
   • i. Let G be (p,q) graph. Show that the following statements are equivalent
2. Q1 G is tree
3. Q2 G is acyclic and +1
4. Q3 G is connected and p = q +1
   • ii. State and prove Cayley’s formula for spanning trees
   • (b) Attempt any TWO questions: i, Define’ connectivity and edge connectivity of a graph G. Prove that vertex connectivity of a graph is less than or equal to edge connectivity of a graph G 12
   • ii. If T is spanning tree of a connected graph G and e is an edge of G that is not in T, then prove that e contains a unique cycle that contains the edge e
   • iii. Use Huffman coding to encode these symbols with the given frequencies: 0.20, b: 0.10, 0.15, 0.25, e: 0.30. what is average number of bits required to encode a character?
   • iv. Let r(G) denote the number of spanning trees of a graph G. If e E(G) is not a loop then prove that = r(G e)
   • (a) Attempt any ONE question: Prove that the cube is connected bipartite with 2* vertices 8
   • ii. If G is a graph on p vertices with p > 3 such that deg(u) + deg(v) 2 p for every pair of non adjacent vertices u and in G, then prove is Hamiltonian
   • (b) Attempt any questions: 12
   • i. Define closure of a graph C(G). Show that if the closure of graph G is complete then
   • ii. Show that the cube graph Q,, > 2 is a Hamiltonian graph 7 If Gis 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
   • iv. Let G be a simple graph with p vertices and q edges with p > 3. Ifq > then prove that Gis Hamiltonian 4, Attempt any THREE questions: (15)
   • (a) If G is a graph of order p and size g, then prove that = 2g. Hence prove that every graph has an even number of odd vertices
   • (b) Show that every nontrivial graph contains at least two vertices which are non cut vertices
   • (c) Show vertex v in a tree T is a cut vertex of T if and only if deg(v) > 1
   • (d) If T is treé with p vertices whose degree is (dj, , then prove that
   • (e) If Gis Hamiltonian graph then for every nonempty proper subset of V(G), prove that
   • (f). Prove that is Hamiltonian if and only

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