First Question is compulsory.

Answer any FOUR from the remaininig questions.

All questions carry wqual marks.

Answer ALL parts of any question at one place.

(a)   Prove that B-A is a subset of   A

(b)   Fill in the blanks in the folliwing arguments:

If the graphs are isomorphic, then their degree spectrum will be the same. Their degree spectra are different. Hence———–

(c)    Write the following staement in predicate calculus:

There is a mother for every person.

(d)   Find the number of permutations of the letters of SCIENTISTS so that the same letters do not appear together.

(e)    Find the number of divisrs of 500.

(f)     Write the adjacency matrix of the following digraph.

(DIAGRAM)

(G)  Define a complete binary tree.

2. (a) Check whether {[p->(qVr)]^(~q)} -> (p->r) is a tautology.

(b) Suppose that a man hiked 6 miles the forst hour and 4 miles the twelfth hour and hiked a total of 71 miles in 12 hours. Prove that he must have hiked at least 12 miles within a certain period of two consecutive hours.

3. (a) Use mathematical induction to prove that n3+1>n2+n for each integer n>=2.

(b)  How many binary sequences are there of lingth 15?.

4. (a) How many integral solutions are there of x1=x2=x3=x4=20 of 1<=x1<=6, 1<=x2<=7, 1<=x2<=8 and 1<=x4<=9?.

(b)  Consider (1+2x)n to prove

C(n,0)+2c(n,1)=22c(n,2)+…….+2nc(n,n)=3n.

5. (a) How many ways are there to paint 20 identical rooms in a hotel with 5 colors if there is only enough blue, pink and green paint to paint 4 rooms?

(b)  Find r, given that Fr=2 F101+f100.

6. (a) Show that the transitive closure of a symmetric relation is symmetric.

(b) Give the sequence merge (A,B) where A=(1,24,95,100,101} and B=(1,24,93,97,101,102}. Show how it is defined in termes of the merges of another sequences.

7.   (a)  Prove that in every non trivial tree there is at least one vertex of degree 1.

(b)  Prove that a graph G is a tree if and only of G has no cycles and |E|=|V|=1.

8.   ( a) State and prove the Euler’s formula for planar graphs.

(b) Determine the chromatic number of the following:

(i) A bipartite graph

(ii) A wheel with 8 vertices W8.

( iii) A complete graph Kn

IT 2.1 Previous PapersCSE,CSE Previous Papers,Discrete Mathematical Structures-I Previous Papers,IT,IT Previous Papers
First Question is compulsory. Answer any FOUR from the remaininig questions. All questions carry wqual marks. Answer ALL parts of any question at one place.  Answer the following: (a)   Prove that B-A is a subset of   A (b)   Fill in the blanks in the folliwing arguments: If the graphs are isomorphic, then their degree spectrum will...