BSc Mathematics SEM VI 2018 19 Apr 2018-19 MATHEMATICS GRAPH THEORY AND COMBINATRICS 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 c be a proper coloring of G = (V, E) using t colors, then the coloring partitions V into
   • (a) t—1 parts (b) t parts
   • ii. If graph G is k-critical then
   • (a) G is acyclic (b) G is disconnected
   • (c) G is connected (d) all of these
   • iii. Which of the following can be a chromatic polynomial?
   • iv. K,, is planar if
   • (a) n>4 (c) n=5 (d) None of these
   • v. A connected planar graph has an equal number of vertices and faces. If there are 20 edges in this graph, the number of vertices
   • vi. If f is a flow network N and P be any f—incrementing path with tolerance > 0, then define a new flow f’ as = e(P) for an forward arc a P , f'(a) = f(a) for an backward arc a P and f(a) = f(a) for other arcs a of N.Then value of f’ equals to
   • (c) same as val f (d) val fxe(P)
   • vii. Let denotes the rook polynomial for the board B of darkened squares consisting of m rows and n columns, then
   • (a) constant term is 1
   • (b) coefficient of is number of ways of placing k non capturing rooks
   • (c) if k > min{m,n}
   • (d). all of the above The number of ways to staircase with 12 steps taking 1 or 2 steps at a time is
   • ix. The number of different system of distinct representatives for the family A; = {2,3,4}, Ao =
   • (a) 4! (b) 3! (c) 9 (d) None of these
   • x. If M is maximum matching then which one of the following statement is true?
   • (a) There does not exists any matching M’ such that |M
   • (b) There does not exists any matching M’ such that
   • (c) There exists any matching M’ such that > |M
   • (d) None of these
2. Q2 (a) Attempt any ONE question from the following: 8 marks
   • i. For graph G of order p and size q, prove that 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
   • ii. For any simple graph G, prove that < < 6(G) where denote the vertex connectivity and denotes the edge connectivity and 6(G) denotes the minimum degree of a graph G
   • (b) Attempt any TWO questions from the following: 12
   • i. State Vizing theorem for edge coloring of graphs. Show that > A(G) where x'(G) denotes edge chromatic number and A(G') denotes the maximum degree of G Give an example of the graph for which = A(G)
   • ii. Let denote the chromatic polynomial of the graph G. If G is simple graph then prove that = e) where is an edge of G
   • ii. If Gis a graph with p vertices and G is its complement of G, then show that + where x(G) is the vertex chromatic number of graph G
   • iv. If G (p,q) graph, then prove that > where x(G) denotes the vertex chromatic number of G:
3. Q3 (a) Attempt any ONE question from the following: 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 from the following: 12
   • i. Show that there is at least one face of every polyhedron is bounded by an n—cycle for Show that the edge e is a loop in G if and only if e* is a bridge in G* where G* is dual
   • iii. Define a value of flow and capacity of cut in network N. If f is any flow and k be any cut in a network N then show that val(f) <
   • iv. If G is a connected simple planar graph with p > 3 vertices, q edges and f regions
4. Q1 Show that if = 3p — 6 then each region is triangle
5. Q2 Deduce that a convex polyhedron with 12 vertices and 20 faces is composed entirely
6. Q4 (a) Attempt any ONE question from the following: 8 marks
   • i. State and prove the necessary and sufficient condition for a family of n sets to have System of Distinct Representative
   • ii. 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
   • (b) Attempt any TWO questions from the following: 12
   • i. Define a rook polynomial. Let be the rook polynomial for the n x m chess board, all squares may have rooks. Show that =
   • ii. Show that a matching M in G is a maximum matching if and only if G contains no
   • iii. Find the coefficient of in (a? What is the coefficient of x”?
   • iv. Let h, denote the number of nonnegative integral solutions of the equation + + + 5e, = n. Find the generating function f(x) for
7. Q5 Attempt any FOUR questions from the following: 20 marks
   • (a) For any graph prove that < A(G) +1 where represents vertex chromatic number of a graph A(G) denotes the maximum degree of G. Give an example of graphs for which y(G) < A(G)
   • (b) Prove that every tree with n vertices is 2-chromatic
   • (c) IfGbea simple connected graph with at least 11 vertices then prove that either G or its complement G must be nonplanar
   • (d) 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
   • (e) Find the rook polynomial for the following
   • (f) Let be a family of sets such that for each k, 1 < k < n and for each choice of < ip <n, +1. Let x be any element of Aj Show that has a system of distinct representatives in which x represents

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