BSc Mathematics SEM V 2017 18 2017-18 Graph Theory And Combinatorics 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: 8 marks
   • i. Prove that a graph G(p,q) with p > 2 is 2-connected if and only if any two vertices are connected by at least two internally disjoint paths
   • ii. If denotes the chromatic polynomial of a (p,q) graph G then prove that
   • (a) The coefficient of k? in is 1
   • (b) The constant term of is zero
   • (c) The terms of are alternate in sign
   • (d) The coefficient of is —q where q is number of edges of G Attempt any TWO questions: (12)
   • i. Define vertex chromatic number of a graph G. If G is a (p,q) graph, then prove that > where denotes the vertex chromatic number of G
   • ii. If G is cubic graph, then show that = where denote the vertex connectivity and denotes the edge connectivity of a graph G
   • iii. State vizing theorem for edge coloring of graph. Show that > A(G) where x/(G) denotes. edge chromatic number and A(G) denotes the maximum degree of G. Give an example of the graph for which = A(G)
   • iv. If Gis a cycle on n vertices then show that 7(G) = (k — 1)" + — 1)
2. Q2 (a) Attempt any ONE question: 8 marks
   • i. State and prove Max Flow - Min Cut Theorem
   • ii. Show that every planar graph is 5 vertex colorable
   • (b) Attempt any TWO questions: 12
   • i. Let f be a flow network N and P be any f-incrementing path then show that there exist a revised flow f’ such that val(f’) = val(f) +
   • ii. State and prove Euler theorem for planar graph ili. Show that edges in a plane graph G form a cycle in G if and only if the corresponding dual edges form a bond in
   • iv. Show that the complete graph and complete bipartite graph are nonplanar
   • Q. P. Code:27508
3. Q3 (a) Attempt any ONE question: 8 marks
   • i. State and prove Hall’s (Marriage) Theorem for a System of Distinct Representatives
   • ii. Derive the recurrence relation for number of ways of dividing a 1—sided. convex polygon into triangular regions by inserting diagonals that do not intersect in the interior and prove using generating function that the solution to this recurrence relation is a Catalan Number
   • (b) Attempt any TWO questions: 12
   • i. Show that a matching M in G is a maximum matching if and only if G contains no
   • ii. Let B denotes a forbidden chess board in which a special square has been identified and let D denote the board obtained from the original board by deleting the row and column containing the special square and E denote the board obtained from the original board where only the special square * is removed from the board, then prove
   • iii. Find the coefficient of in a4 What is the coefficient of x”?
   • iv. Solve recurrence relation a, = (n > 1) subject to initial condition with ap = 1
4. Q4 Attempt any THREE questions: 15 marks
   • (a) Lel denote the chromatic polynomial of the graph G. If G is simple graph then prove that = — e) — where e is an edge of G
   • (b) Define k—critical graph. If G is k—critical graph then show that 6(G) > k—1, where 6(G) denotes the minimum degree of G
   • (c) Show that there is at least one face of every polyhedron is bounded by an n—cycle for
   • (d) Prove that for any flow f and any cut val(f) = —
   • (e) Define System of distinct representatives for a family of sets and hence determine the number of distinct. system of representatives for the family A, = {1,2}, = {2,3}, A3 = = = {5,1}. Generalize your result for n
   • (f) Find the rook polynomial for the following

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