**Combanatorics and Graph Theory (Elective-I) Question **

**Papers Andhra University**

**B. Tech (CSE) Degree Examination**

**Forth Year – First Semester**

**COMBANATORICS AND GRAPH THEORY (ELECTIVE-I)**

**Effective from the admitted batch of 2004-2005**

Time: 3 hrs

Max Marks: 70

First Question is Compulsory

Answer any four from the remaining questions

All Questions carry equal marks

Answer all parts of any question at one place

1. a) State pigeonhole principle.

b) Prove that the product of three consecutive integers is divisible by 6.

c) Differentiate between a combination and a permutation.

d) State multinomial theorem.

e) Write the generating function for the number of ways of selecting r balls from 3 red, 5 blue and 7 black balls.

f) Prove or disprove If every vertex of a simple graph G has degree 2, then G is a cycle.

g) Check whether 5,5,5,3,2,2,1,1 is a graphic sequence or not

2. a) Prove that C(n,r) C(n,k) = C(n,k) C(n-k, r-k) for integers n ≥ r ≥ k ≥ 0.

b) Find the number of integral solutions of the equation x_{1} + x_{2} + x_{3} = 20 if 2 ≥ x_{1} ≥ 6,3≥x_{2} ≥ 7,5 ≥ x_{3} ≥ 8,1 ≥ x_{4} 9.

3. a) Find and solve a recurrence relation for the number of n-digit binary sequences with no triple of consecutive 1’a.

b) Solve the recurrence relation a_{n} – 5_{n-1} + 6_{n-2} where a_{o} = and a_{1}=5.

4. a) State and prove Vandermonde’s Identity of combinatorics.

b) Determine the coefficient of x^{5} y^{10} z^{5} w^{5} in (x – 7y + 3_{z-w})_{25}

5. a) Explain the terms: bipartite graph. connected component and cut-vertex of a graph

b) Prove that a digraph is strongly connected if and only for each partition of the vertex set into nonempty sets S and T, there is an edge from S to T.

6. a) Define the terms: Eccentricity, Center and Radius of Graph.

b) Describe an algorithm for finding the strong components of a given digraph.

7. a) Model the problem of network flow as a graph theoretic problem.

b) Describe Ford-Fulkerson labeling Algorithm on network flows

8. a) Explain the terms: Clique of a Graph, Color critical Graphs and Complete multipartite graph.

b) Find the minimum number of edges in a connected n-vertex graph with chromotic number k.