BSc Mathematics SEM VI 2019 20 Nov 2019-20 ATKT MATHEMATICS GRAPH THEORY AND COMBINATORICS 75/25 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 k — 1 degree
4. 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: 12
   • i. Show that vertex connectivity of a graph G is always less or equal to the edge connec
   • 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
   • iii. Show that a connected graph G on p vertices is a tree if and only if the chromatic polynomial of G is k(k
   • iv. For any graph G, prove that < A(G)+1 where 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)
5. Q2 (a) Attempt any ONE question: 8 marks
   • i. State and prove Max Flow - Min Cut Theorem
   • 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. 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
   • iii. If G is a graph with p vertices and q edges, and let every vertex of G has degree at least 6 then prove that > 3p. Hence prove that every planar graph contains a vertex of degree at most. 5
   • iv. Show that the complete graph and complete bipartite graph are nonplanar Paper Subject Code: 10259 Mathematics: Paper IV -Graph Theory and Combinatorics. (R-2016-17)
6. Q3 (a) Attempt any ONE question: 8 marks
   • i. State and prove Hall’s (Marriage) Theorem for a System of Distinct Representatives
   • 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: 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. Show that the number of non-negative integer solutions of the equation is given by
   • iv. Solve recurrence relation a, = (n > 2) subject. to initial conditions with
7. Q4 Attempt any THREE questions: 15 marks
   • (a) Determine the chromatic polynomial and chromatic number of a graph G obtained by deleting an edge from K4
   • (b) 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
   • (c) Prove that for any flow f and any cut val(f) = f*(S) —
   • (d) Show that the edge e is a loop in G if and only if e* is a bridge in G
   • (e) Let h, denote the number of non-negative integral solutions of the equation + + 2e3 + Find the generating function f(x) for ho,
   • (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.