BSc Sem VI 2022 2023 Apr 2023 MATHEMATICS GRAPH THEORY AND COMBINATORICS Question Paper - Mumbai University | munotes

Questions asked in this paper

• 2) Figures to the right indicate full marks

1. Q1 (a) Attempt any ONE question: 8 marks
   • i. For graph G of order p and size q, prove that 7(G), the chromatic polynomial of the graph G, is monic polynomial of degree p in k with integer coefficients and constant term zero. Further prove that its coefficients are alternate in sign and the coefficient of is —q
   • ii. If G= K,, is complete graph with n vertices, n > 2 then prove that an edge chromatic J n—1 ifn is even, number x'(G) = n if n is odd
   • (b) Attempt any TWO questions: 12
   • i. Define a chromatic polynomial of graph G. Determine the chromatic polynomial and chromatic number of a graph G obtained by deleting an edge from
   • ii. If G is a cycle on n vertices then show that = (k — 1)" + — 1)
   • iii. Show that vertex connectivity of a graph G is always less or equal to the edge connec
2. Q2 (a) Attempt any ONE question: 8 marks
   • i. Show that every planar graph is 5 vertex colorable
   • ii. Show that there are exactly five regular Polyhedra
   • (b) Attempt any TWO questions: 12
   • i. State and prove Euler theorem for planar graph
   • ii. Let G* denote dual graph of G. Show that the edge e is a loop in G if and only if e is a bridge in
   • iii. Let f be a flow in a network N and P be any f-incrementing path then show that there exist a revised flow f’ such that val(f’) = val(f) +
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 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
   • (b) Attempt any TWO questions: 12
   • i. Let be the rook polynomial for the n x m chess board, all squares may have rooks. Show that = + Paper Subject Code: 88682 Mathematics: Graph Theory and Combinatorics (R-2023)
   • ii. Find the number h,, of bags of fruit 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 a multiple of 5, the number of oranges is at most 4, and the number of pears is 0 or 1
   • iii. Find the number of integral solutions of the equation
4. Q4 Attempt any THREE questions: 15 marks
   • (a) Define k—critical graph. If G is k— critical graph then show that 6(G) > k—1 where is minimum degree of G
   • (b) Show that x/(G) > A(G) where denotes edge chromatic number and A(G) denotes the maximum degree of G. Give an example of the graph for which = A(G)
   • (c) Show that there is at least one face of every polyhedron is bounded by an n—cycle for
   • (d) If f is any flow and be any cut in a network N then show that val(f) < cap(K)
   • (e) Solve recurrence relation a, = > 1 given aj = 1 by using generating function Find a recurrence relation for the ways to distribute n identical balls into k distinct boxes with between two and four balls in each box. Repeat the problem with balls of three colors

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