BSc Mathematics SEM VI 2018 19 May 2018-19 MATHEMATICS IV GRAPH THEORY & 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. If G is k— critical graph then show that
2. Q1 G is connected
3. Q2 Every vertex v of graph G has atleast — 1 degree
4. Q3 Graph G cannot be partitioned into subgraphs
   • ii. For any simple graph G, prove that < 6(G) where denote the vertex connectivity and denotes the edge connectivity and 5(G) denotes the minimum degree of a graph G
   • (b) Attempt any TWO questions: 12
   • i. Define vertex chromatic number Let G be the graph with p vertices. Show that x(G) = Where x(G) denotes vertex chromatic number of G and 6(G) denotes minimum degree of G
   • ii. Show that every tree with n > 2 vertices is 2-chromatic. Is converse true? Justify
   • iii. If G be a connected graph that is not an odd cycle, then prove that G has a 2-edge colouring in which both colours are representing at each vertex of degree at least two
   • iv. Show that if are n components of graph G then 7(G) = I]
5. Q2 (a) Attempt any ONE question: 8 marks
   • i. Show that every planar graph is 5 vertex colorable
   • ii. State and prove Max Flow - Min Cut Theorem
   • (b) Attempt any TWO. questions: 12
   • i. Define dual graph G* of G. 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
   • ii. Show that there is at least one face of every polyhedron is bounded by an n—cycle for
   • iii. Show that every planar graph is 6-vertex colorable
   • iv. State and prove Euler theorem for planar graph 19F968895380187F5405CE39D2ECD4BE Paper Subject Code: 10259 Mathematics: Paper IV -Graph Theory and Combinatorics. (R-2016-17)
6. Q3 (a) Attempt any ONE question: 8 marks
   • i. Derive the recurrence relation for number of ways of dividing 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. Let G be a bipartite graph with bipartition Show that if G contains a matching that saturates every vertex in X if and only if |N(S)| > |S| for all S
   • (b) Attempt any TWO questions: 12
   • i. Define a rook polynomial. Prove that if B is a board of darkened squares that. de composes into the two disjoint sub boards B, and then prove that = B,) R(x, where R(x, B) is a rook polynomial for board B
   • ii. Determine the generating function for the number of n-combinations of apples, ba nanas, oranges, and pears, where, in each n-combination, the number of apples is even, the number of bananas is odd, the number of oranges is between 0 and 4, and there is at least one pear
   • iii. If An} 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 Aj, —k) for all choices of k = 1,2,.n and all choices of with < <n
   • iv. How many nonnegative integer solutions are there to the equation = 26 with >0 and 2; > 0 for 7 = 5
7. Q4 Attempt any THREE questions: 15 marks
   • (a) For any graph G, prove that x(G) < A(G) + 1 where x(G) represents vertex chromatic number of a graph G and A(G) denotes the maximum degree of G. Give an example of graphs for which < A(G)
   • (b) If G is a (p,q) graph, then prove that > where x(G) denotes the vertex chromatic number. of G
   • (c) If fis flow in a network N and P is any f—incrementing path, then show that there exists a revised flow f’ such that valf’ > valf
   • (d) If Gbea simple connected graph with at least 11 vertices then prove that either G or its complement G must be nonplanar
   • (e) Solve recurrence relation + for all n > 2 subject to initial conditions = = {1,3,5}. Does family A have an System of Distinct Representa tive? If not, what is the largest number of sets in the family with an System of Distinct 19F968895380187F5405CE39D2ECD4BE

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