## Graph Theory and Combinatorics - Dec 2012

### Computer Science Engg. (Semester 4)

TOTAL MARKS: 100

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **four** from the remaining questions.

(3) Assume data wherever required.

(4) Figures to the right indicate full marks.
**1 (a)** Define a connected graph. Prove that a connected graph with n vertices has at least (n-1) edges.(6 marks)
**1 (b)** Define isomorphism of two graphs. Determine whether the two graphs (Fig Q1(b) (i)) and (Fig Q1(b) (ii))

(7 marks)
**1 (c)** Define a complete graph. In the complete graph with n vertices, where n is an odd number ≥3, show that there are (n-1)/2 edge disjoint Hamilton cycles.(7 marks)
**2 (a)** Design a regular graph with an example. Show that the Peterson graph is non planar graph.(7 marks)
**2 (b)** Prove that a graph is 2-chromatic if and only if it is a null bipartite graph.(6 marks)
**2 (c)** Define Hamilton and Eulerian graphs. Prove the complete graph K_{3,3} is Hamilton but not Eulerian.(7 marks)
**3 (a)** Define a tree. Prove that a connected graph is a tree if it is minimally connected.(6 marks)
**3 (b)** Define a spanning tree. Find all the spanning trees of the graph given below. (Fig Q3(b))

(7 marks)
**3 (c)** Construct a optimal prefix code for the symbols a, o, q, u, y, z that occur with frequencies 20, 28, 4, 17, 12, 7 respectively.(7 marks)
**4 (a)** Define matching edge connectivity and vertex connectivity. Give one example for each.(6 marks)
**4 (b)** Using Prim's algorithm, find a minimal spanning tree for the weighted graph shown in the following Fig Q4(b).

(7 marks)
**4 (c)** Three boys b_{1}, b_{2}, b_{3}, b_{4} and girls g_{1}, g_{2}, g_{3}, g_{4} are such that

b_{1} is a cousin of g_{1}, g_{2} and g_{4}

b_{2} is cousin of g_{2} and g_{4}

b_{3} is a cousin of g_{2} and g_{3}.

If a boy must marry a cousin girl, find possible sets of such couples.(7 marks)
**5 (a)** Find the number of ways of giving 10 identical gift boxes to six person A, B, C, D, E, F in such a way that the total number of boxes given to A and B together does not exceed 4.(6 marks)
**5 (b)** Define Catalan number. In how many ways can one travel in the xy plane from (0, 0) to (3, 3) using the moves R:(x+1, y) and U:(x, y+1) if the taken may touch but never rise above the line y=x? Draw two such paths in the xy plane.(7 marks)
**5 (c)** Determine the coefficient of

i) xyz^{2} in the expansion of (2x-y-z)^{4}

ii) a^{3}b^{3}c^{2}d^{5} in the expansion of (a+2b-3c+2d+5)^{16}(7 marks)
**6 (a)** How many integers between 1 and 300 (inclusive) are

i) divisible by 5, 6, 8?

ii) divisible by none of 5, 6, 8?(7 marks)
**6 (b)** In how many ways can the integers 1, 2, 3, ....., 10 be arranged in a line so that no even integer is in it natural place?(6 marks)
**6 (c)** Find the rook polynomial for the following board (Fig Q6(c)).

(7 marks)
**7 (a)** Find the coefficient of x^{18} in the following products: $$ i) \ (x+x^2+x^3+x^4+x^5)(x^2+x^3+x^4+x^5+\cdots \ \cdots)^5 \\ ii) (x+x^3+x^5+x^7+x^9)(x^3+2x^4+3x^5+ \cdots \ \cdots )^3 $$(7 marks)
**7 (b)** Using the generating function find the number of i) non negative and

ii) positive integer solutions of the equation x_{1}+x2+x_{3}+x_{4}=25(6 marks)
**7 (c)** Find all the partitions of x^{7}.(7 marks)
**8 (a)** Solve the Fibonacci relation.

F_{n+2}=F_{n+1}+F_{n} for n≥ 0 given F_{0}=0 and F_{1}=1.(7 marks)
**8 (b)** Solve the recurrence relation

a_{n-2} a_{n-1} + a_{n-2} =5_{n}.(7 marks)
**8 (c)** Find a generating function for the recurrence relation

a_{r}+5a_{r-1} +6a_{r-2} = 3r^{2}, r≥2.(6 marks)