BSc Mathematics SEM VI 2016 17 2016-17 Graph Theory & 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. For graph G of order p and size q, prove the chromatic polynomial of the graph G, is monic polynomial of degree p in with integer coefficients and constant term zero. Further prove that its coefficients are alternate in sign and the coefficient of is —q
   • ii. Prove that a graph G with p > 2 is 2-connected if and only if any two vertices are connected by at least two internally disjoint paths
   • (b) Attempt any TWO questions: 12
   • i. Show that vertex connectivity of a graph G is always less or equal to the edge connec
   • ii. Show that a connected graph G on n vertices is a tree if and only if the chromatic polynomial of Gis k(k
   • iii. Lel denote the chromatic polynomial of the graph G. If G is simple graph then prove that = 7(G —e) — where e is an edge of G
   • iv. Show that every tree with n > 2 vertices is 2-chromatic. Is converse true? Justify
2. Q2 (a) Attempt any ONE question: 8 marks
   • i. Show planar graph is 5 vertex colorable
   • ii. Show that there are exactly five regular polyhedra
   • (b) Attempt any TWO questions: 12
   • i. Show that 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
   • ii. Let f be a flow in a network N and P be any f-incrementing path then show that there exist a revised flow such that val(f’) = val(f) +
   • iii. 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 if Gis a planar graph in which degree of each face is 3, then q(G) = 3p—6
3. Q3 (a) Attempt any ONE question: 8 marks
   • i. An elf has a staircase of n stairs to climb. Each step it takes can cover either one stair or two stairs. Find a recurrence relation for a,, the number of different ways for the elf to ascend the n—stair staircase and solve it by using generating function
   • 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. 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 A;, U---U for all choices of k = 1,2,.n and all choices of with 1 <n
   • ii. Let be the rook polynomial for the n x m chess board, all squares may have rooks. Show that =
   • iii. Solve recurrence relation = + for all n > 2 subject to initial conditions
   • iv. Find the coefficient of in (x? What is the coefficient of
4. 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) Determine the chromatic polynomial and chromatic number of a graph G obtained by deleting an edge from
   • (c) If G is planar graph with n vertices, m edges, f regions and k components then prove that
   • (d) If f is any flow and be any cut in a network N then show that val(f) < cap(K) Show that a matching M in G is a maximum matching if and only if G contains no
   • (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.