MORE IN Graph Theory and its Applications
VTU Computer Science (Semester 4)
Graph Theory and its Applications
December 2012
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1 (a) Define a connected graph. Prove that a connected graph with n vertices has at least (n-1) edges.
6 M
1 (b) Define isomorphism of two graphs. Determine whether the two graphs (Fig Q1(b) (i)) and (Fig Q1(b) (ii))
7 M
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 M

2 (a) Design a regular graph with an example. Show that the Peterson graph is non planar graph.
7 M
2 (b) Prove that a graph is 2-chromatic if and only if it is a null bipartite graph.
6 M
2 (c) Define Hamilton and Eulerian graphs. Prove the complete graph K3,3 is Hamilton but not Eulerian.
7 M

3 (a) Define a tree. Prove that a connected graph is a tree if it is minimally connected.
6 M
3 (b) Define a spanning tree. Find all the spanning trees of the graph given below. (Fig Q3(b))
7 M
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 M

4 (a) Define matching edge connectivity and vertex connectivity. Give one example for each.
6 M
4 (b) Using Prim's algorithm, find a minimal spanning tree for the weighted graph shown in the following Fig Q4(b).
7 M
4 (c) Three boys b1, b2, b3, b4 and girls g1, g2, g3, g4 are such that
b1 is a cousin of g1, g2 and g4
b2 is cousin of g2 and g4
b3 is a cousin of g2 and g3.
If a boy must marry a cousin girl, find possible sets of such couples.
7 M

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 M
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 M
5 (c) Determine the coefficient of
i) xyz2 in the expansion of (2x-y-z)4
ii) a3b3c2d5 in the expansion of (a+2b-3c+2d+5)16
7 M

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 M
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 M
6 (c) Find the rook polynomial for the following board (Fig Q6(c)).
7 M

7 (a) Find the coefficient of x18 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 M
7 (b) Using the generating function find the number of i) non negative and
ii) positive integer solutions of the equation x1+x2+x3+x4=25
6 M
7 (c) Find all the partitions of x7.
7 M

8 (a) Solve the Fibonacci relation.
Fn+2=Fn+1+Fn for n≥ 0 given F0=0 and F1=1.
7 M
8 (b) Solve the recurrence relation
an-2 an-1 + an-2 =5n.
7 M
8 (c) Find a generating function for the recurrence relation
ar+5ar-1 +6ar-2 = 3r2, r≥2.
6 M

More question papers from Graph Theory and its Applications