BSc Mathematics SEM VI 2019 20 Nov 2019-20 ATKT 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 Choose correct alternative in each of the following: 20 marks
   • i. Let G be aconnected graph. If G is neither complete nor an odd cycle then vertex chromatic number of G is
   • (a) < Max degree of G. (b) = Maximum degree of G
   • (c) = Max degree of (d) None of these
   • ii. Edge Chromatic number of > 2 is
   • (c) n+1 (d) None of the above
   • iii. The relation between vertex connectivity edge connectivity and minimum degree 6 is
   • (c) (d) None of these
   • iv. If G(p,q) be planar graph, then sum of degrees of regions is equal to
   • (c) p+q None of these
   • v. Let G be a connected planar graph with edges, p vertices and f regions then
   • vi. If f is a flow in a network N be any subset of nodes, then is a cut if
   • (a) S,yis not in (b) in S,yes
   • (c) x is not in S,y is not in S (d)
   • vii. If the polynomial 3x + x? is a rook polynomial of some chess board then
   • (c) (d) cis even
   • viii. The function e~” is the generating function of the sequence
   • (a) On (b) = =
   • ix. The number of different system of distinct representatives of the family A; = {1,2}, =
   • x. A matching M in G is a maximum matching if and only if G contains
   • (a) no M-augmenting path. (b) M-augmenting path
   • (c) no M-alternating path. (d) None of these
2. Q2 (a) Attempt any ONE question from the following: 8 marks
   • i. If G is k— critical graph then show that
3. Q1 G is connected
4. Q2 Every vertex v of graph G has at least k — 1 degree
5. Q3 Graph G cannot be partitioned into subgraphs
   • 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 from the following: 12
   • i. Define vertex chromatic number Let G be the graph with n vertices. Show that x(G) > where y(G) denotes vertex chromatic number of Gand 6(G) denotes minimum degree of G
   • ii. If G is a cycle on n vertices then show that 7,(G) = (k + (—1)"(k —1)
   • iii. If G is cubic graph, then show that = where denote the vertex connectivity and (G) denotes the edge connectivity of a graph G
   • iv. If G is a bipartite graph, then show that = A(G), where represents vertex chromatic number of a graph G and A(G) denotes the maximum degree of G
6. Q3 (a) Attempt any ONE question from the following: 8 marks
   • i. State and prove Euler’s formula for planar graphs. Hence or otherwise prove that the minimum degree of a simple planar graph is < 5
   • ii. State and prove Max Flow - Min Cut Theorem
   • (b) Attempt any TWO questions from the following: 12
   • i. Define dual graph G* of G. Show in a plane graph G form a cycle in G if and only if the corresponding dual edges form a bond in
   • ii. Let f be a flow in a network N and P be any path then show that there exist a revised flow f’ such that val(f’) = val(f) +
   • iii. For a plane graph G, prove that bipartite if and only if every face of G has even
   • iv. Show that there is at least one face of every polyhedron is bounded by an n—cycle for
7. Q4 (a) Attempt any ONE question from the following: 8 marks
   • i. State and prove Hall’s (Marriage) Theorem for a System of Distinct Representatives
   • ii. 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
   • (b) Attempt any TWO questions from the following: 12
   • i. Let B denotes a forbidden chess board in which a special square * has been identified and 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
   • ii. Show that a matching M in G is a maximum matching if and only if G contains no
   • iii. 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
   • iv. Solve the recurrence relation a, = + 2, with = 1 using generating function
8. Q5 Attempt any FOUR questions from the following: 20 marks
   • (a) Show that vertex connectivity of a graph G is always less or equal to the edge connectivity
   • (b) Show that if are n components of graph G then = I]
   • (c) Show that every planar graph is 6-vertex colorable
   • (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 Show that the number of nonnegative integer solutions of the equation is given by ‘ {2,3},A5 = {1}, = {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

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