BSc Mathematics SEM VI 2016 17 2016-17 Graph Theory & Combinatrics II 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. State and prove Euler’s fromula for planar graphs. Hence or otherwise prove that the minimum degree of a simple planar graph is < 5
   • ii. If 7,(G) denotes the chromatic polynomial of a (p,q) graph G then prove that
2. Q1 The coefficient of k? in is 1 2)The constant term of is zero 3)The terms of are alternate in sign 4)The coefficient of k?~' is —q where q is number of edges of G
   • (b) Attempt any TWO questions: 12
   • i. Define vertex chromatic number of a graph G. For any 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. Show that every planar graph is 6-vertex colorable
   • iii. Show that if are n components of graph G then = I]
   • iv. Show that a graph G on n vertices is a tree if and only if the chromatic polynomial of
3. 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 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 > valf Let be a family of sets such that for each k, 1 < k < n and for each choice of 1 < 4 < ig U Ai, > +1. Let be any element of Show that has a system of distinct representatives in which x represents Aj
   • iii. Prove that for any flow f and any cut val(f) = ft(S) —
   • iv. If bea 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 for all choices of k = and all choices of with 1 <n
   • Q. P. Code: 05009
4. Q3 (a) Attempt any ONE question: 8 marks
   • i. Let C,, denote the number of ways of dividing a convex polygon with (n + 2)-gon into triangular regions by inserting diagonals that do not intersect in the interior and let Co = 1. Show that = for n > 1 and by 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 takking 1 or 2 steps at a time and solve it using generating function
   • (b) Attempt any TWO questions: 12
   • i. 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
   • ii. Show that the number of nonnegative integer solutions of the equation is given by
   • iii. Let be the rook polynomial for the n x m chess board, where all squares may have rooks. Show that =
   • iv. Solve recurrence relation + for > 2 subject to initial conditions
5. Q4 Attempt any THREE questions: 15 marks
   • (a) Let G be the graph with n vertices. Show that > Where x(G) denotes vertex chromatic number of G and 6(G) denotes minumum degree of G
   • (b) Define a line graph of a graph. Show that a simple connected graph G is isomrophic to its line graph if and only if it a cycle
   • (c) Define System of distinct representatives for a family of sets. Let A = (Aj, Ag, A3, Au, As, Ao), 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?
   • (d) 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
   • (e) Prove that if B is a board of darkened squares that decomposes into the two disjoint sub boards and then prove that R(x, B) = R(x, where R(x, B) is a rook polynomial for board B
   • (f) Find the number h,, of bags of fruits that can be made out of apples , bananas, oranges and pears, where, in each bag, the number of apples is even, the number of bananas is multiple of 5, the number of oranges is at most 4, and the number of pears is 0 or 1

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