BSc Mathematics SEM V 2017 18 2017-18 Graph Theory And Combinatorics II PAPER IV 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. Show that every planar graph is 5-vertex colorable
   • ii. State and prove Euler’s fromula for planar graphs. Hence or otherwise prove that. the minimum degree of a simple planar graph is < 5
   • (b) Attempt any TWO questions: 12
   • i. Define vertex chromatic number of a simple finite graph G. Prove that x(G) < A(G) + 1 where represents vertex chromatic number of a graph G and A(G) denotes the maximum degree of G
   • ii. If G is a planar (p,q) graph in which every face is bounded by a cycle of length at least n, then show that
   • iii. For a simple graph G of order p and size q, prove that the chromatic polynomial of the graph G, is monic polynomial of degree p in k with integer coefficients and
   • iv. Show that for a cycle C,, of length n, the chromatic polynomial 7; is given by
2. Q2 (a) Attempt any ONE question: 8 marks
   • i. State and prove Max Flow-Min Cut Theorem
   • ii. State and prove the necessary and sufficient condition for a family of n sets to have System of Distinct Representative
   • (b) Attempt any TWO questions: 12
   • i. Define val(f), value of flow f. If f is flow in a network N and P is any f—incrementing path, then show that there exists a revised flowf’ such that val f’ > valf
   • ii. Show that the number of different system of distinct representatives for the family A; = {1,2,.,n}— {i}, 1 is D,, the number of derangements on n symbols
   • iii. Prove that for any flow f and any cut val(f) = —
   • iv. If be a family of set, then prove that the largest number of sets of the family which together have a system of distinct representative equals the minimum value of expression A;, U---U for all choices of k = 1,2,.n and all choices of with 1 <n
   • Q. P. Code:27507
3. Q3 (a) Attempt any ONE question: 8 marks
   • i. Derive the recurrence relation for number of ways of dividing a (n+ 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
   • ii. Derive the recurrence relation to climb a staircase with n steps by taking 1 or 2 steps at a time and solve it using generating function
   • (b) Attempt any TWO questions: 12
   • i. Let B denotes a forbidden chess board in which a special square * has been identified 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 that
   • ii. Derive the recurrence relation for the number of regions into which the plane is divided by n straight lines, no two of which are parallel and no three of which are concurrent Furthermore using generating function, show that the solution of the above recurrence
   • iii. Solve recurrence relation a, = for all n > 2 subject to initial conditions a, = 1
   • iv. Show that the number of nonnegative integer solutions of the equation is given by
4. Q4 Attempt any THREE questions: 15 marks
   • (a) Show that a connected graph G on n vertices is a tree if and only if the chromatic polyno mial of G is k(k
   • (b) 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)
   • (c) If f is any flow and K be any cut in a network N with val(f) = then show that f is maximum flow and K is minimum cut
   • (d) Define System of distinct representatives for a family of sets. Let A = (Aj, Ag, A3, Au, As, Does family A have an System of Distinct Representative? If not, what is the largest number of sets in the family with an System of Distinct Representative?
   • (e) Prove that if B board of darkened squares that decomposes into the two disjoint sub boards B; and then prove that R(x, B) = R(x, where R(x, B) is a rook polynomial for board B
   • (f) denote the number of nonnegative integral solutions of the equation + 4e2 + 2e3 + = n, find generating function for hy

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