## Graph Theory and Combinatorics - Jun 2015

### 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)** For the following graph determine,

i) A walk from b to d that is not trail

ii) A b-d trail that is not path

iii) A path from b to d

iv) A closed walk from b to b that is not a circuit

v) A circuit from b to b that is not a cycle

vi) A cycle from b to b
(6 marks)
**1 (b)** Define subgraph, spanning subgraph , induced subgraph and complete graph with example(7 marks)
**1 (c)** Prove that the undirected graph G=(V,E) has an Euler circuit if and only if G is connected and every vertex in G has even degree(7 marks)
**2 (a)** Define planar graph and prove that the following Petersen graph is nonplanar using Kuratowski's theorem
(6 marks)
**2 (b)** Prove that in a complete graph with n-vertices, where n is an add number ≥ 3, there are (n-1)/2 edge-disjoint Hamiltonian cycles(7 marks)
**2 (c)** Find the chromatic polynomial for the following graph
(7 marks)
**3 (a)** Prove that in every tree T=(V,E)$$\left | V \right |=\left | E \right |+1$$(6 marks)
**3 (b)** If T_{1}=(V_{1},E_{1}) and T_{2}=(V_{2},E_{2}) be two trees where $$\left | E_{1} \right |=17$$ and $$\left | V_{2} \right |=2\left | V_{1} \right |$$, then find $$\left | V_{1} \right |,\left [ V_{2} \right ] and \left | E_{1} \right |$$

ii) Let F_{2}=(V_{2},E_{2}) is a forest with $$\left | V_{2} \right |=62 and \left | E_{2} \right |=51$$ , how many trees determine F_{2}

iii) Let F_{1}=(V_{1},E) be a forest of 7 trees where $$\left | E_{1} \right |=40$$ what is $$\left | V_{1} \right |?$$(7 marks)
**3 (c)** Construct an optional 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)** Using the Kruskal's algorithm, find a minimal spanning three of the following weighted graphs
(8 marks)
**4 (b)** Using the Dijkstra's algorithm obtain the shortest path from vertex 1 to each of the other vertices in the following graph
(7 marks)
**4 (c)** Prove that in bipartite graph G(V_{1},V_{2},E) if there is positive integer M such that the degree of every vertex in V_{1}≥M≥ the degree of every vertex in V_{2} then there exists a complete matching from V_{1} to V_{ 2}(7 marks)
**5 (a)** i) How many arrangements all there for all letters in the word SOCIOLOGICAL?

ii) In how many of these arrangements, A and G are adjacent?

iii) In how many of these arrangements, all the vowels are adjacent>(6 marks)
**5 (b)** Determine to co-efficient of :

i) x^{9}y^{3} in the expansion of (2x-3y)^{12}

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

iii) x^{2}-y^{2}-z^{3} in the expansion of (3x-2y-4z)^{7}(7 marks)
**5 (c)** Determine the number of integer solutions for :x_{1}+x_{2}+x_{3}+x_{4}+x_{5}<40,

where:

i) x_{i}≥0, 1≤i≤5

ii)x_{i}≥-3,1≤i≤5(7 marks)
**6 (a)** Find the number of integers between 1 to 10,000 inclusive, which are divisible by none of 5,6 or 8(6 marks)
**6 (b)** Determine in how many ways can the letter in the word ARRANGEMENT be arranged so that there are exactly two pairs of consecutive identical letters(7 marks)
**6 (c)** i) Find the rook polynomial for the shaded chessboard

ii) Let A={1,2,3,4} and B={u,v,w,x,y,z}. How many one to one functions f:A → B satisfy none of the following conditions:

C

_{1}:f(1)=u or v; C

_{2}:f(2)=w; C

_{3}:f(3)=W or x; C

_{4}: f(4)=x,y or z (7 marks)

**7 (a)**Find the coefficient of x

^{15}in $$\dfrac{(1+x)^{4}}{(1-x)^{4}}$$(6 marks)

**7 (b)**A ship carries 48 flags, 12 each of the colours red, white, blue and black. Twelve of these flags are placed on an vertical pole in order to communicate a signal to other ships. Determine, how many of these signals have at least three white flags or no white flags at all(7 marks)

**7 (c)**Find the formula to express : 0

^{2}+1

^{2}+2

^{2}+--------+n

^{2}as a function of n using summation on operator(7 marks)

**8 (a)**Solve the recurrence relation F

_{n+2}=F

_{n+1}+F

_{n}where n ≥ 0 and F

_{0}=0 and F

_{1}=1(6 marks)

**8 (b)**i) A bank pay 6%interest compounded quarterly. If Laura inverts $ 100 then how many months must she wait for her money to double?

ii) The number of bacteria in culture is 1000 and this number increase 250% every 2 hours. Use a recurrence relation to determine the number to bacteria present after one day.(7 marks)

**8 (c)**Solve the recurrence relation :a

_{n+2}-5a<sub<n+1< sub="">+6a

_{n}=2, n≥0, a

_{0}=3, a

_{1}=7 using method of generating functions</sub<n+1<><>(7 marks)