STUPIDSID
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.
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
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?
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
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.
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.
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.
ar+5ar-1 +6ar-2 = 3r2, r≥2.
6 M
More question papers from Graph Theory and its Applications