MODEL PAPER

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₁ + x₂ + x₃ = 20 if 2 ≥ x₁ ≥ 6,3≥x₂ ≥ 7,5 ≥ x₃ ≥ 8,1 ≥ x₄ 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₁=5.

4. a) State and prove Vandermonde’s Identity of combinatorics.
b) Determine the coefficient of x⁵ y¹⁰ z⁵ w⁵ in (x - 7y + 3_z-w)₂₅

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.