1 (a)
Prove by mathematical induction x

^{n}-y^{n}is divisible by x-y.
5 M

1 (b)
How many vertices are necessary to construct a graph with exactly 6 edges in which each vertex is of degree 2.

5 M

1 (c)
Show that a relation is reflexive and circular if and only if it is an equivalence relation.

5 M

1 (d)
Prove that the set G={1,2,3,4,5,6} is an abelian group under multiplication modulo 7.

5 M

2 (a)
Is it possible to draw a tree with five vertices having degrees 1,1,2,2,4?

4 M

2 (b)
Find how many integers between 1 and 60 are

i) not divisible by 2 nor by 3 and nor by 5.

ii) Divisible by 2 but not by 3 and nor by 5.

i) not divisible by 2 nor by 3 and nor by 5.

ii) Divisible by 2 but not by 3 and nor by 5.

8 M

2 (c)
Solve the recurrence relation a

_{r+2}-a_{r+1}-6a=4.
8 M

3 (a)
Show that A?(B?C)=(A?B)?(A?C)

4 M

3 (b)
State and explain Pigeonhole principle, extended Pigeonhole principle. How many numbers must be selected from the set {1,2,3,4,5,6} to guarantee that at least one pair of these numbers add up to 7?

8 M

3 (c)
Let R be a relation on set A={1,2,3,4}, given as

R={(1,1), (1,4), (2,2), (2,3), (3,2), (3,3), (4,1), (4,4)}.

Find transitive closure using Warshall's Algorithm.

R={(1,1), (1,4), (2,2), (2,3), (3,2), (3,3), (4,1), (4,4)}.

Find transitive closure using Warshall's Algorithm.

8 M

4 (a)
Find the generating function for the following sequence

i) 1,2,3,4,5,6......

ii) 3,3,3,3,3......

i) 1,2,3,4,5,6......

ii) 3,3,3,3,3......

4 M

4 (b)
Show that the (2,5) encoding function e:B

e(00)=00000 e(01)=01110

e(10)=10101 e(11)=11011 is a group code.

How many errors will it detect and correct.

^{2}?B^{5}defined bye(00)=00000 e(01)=01110

e(10)=10101 e(11)=11011 is a group code.

How many errors will it detect and correct.

8 M

4 (c)
Draw Hasse Diagram of D

_{42}. Find the complement of each element in D_{42}.
8 M

5 (a)
Define Distributive Lattice along with one appropriate example.

4 M

5 (b)
Let the functions f,g and h defined as follows:

f:R→R, f(x)=2x+3

g:R→R, g(x)=3x+4

h:R→R, h(x)=4x

Find gof, fog, hof, gofoh

f:R→R, f(x)=2x+3

g:R→R, g(x)=3x+4

h:R→R, h(x)=4x

Find gof, fog, hof, gofoh

8 M

5 (c)
\[ Let \ H= \begin{vmatrix}
1 &0 &0 \\0 &1 &1 \\1 &1 &1 \\1 &0 &0 \\0
&1 &0 \\0 &0 &1 \end{vmatrix} \] Be a parity check matrix. Determine the group code e

_{H:}B^{3}? B^{6}.
8 M

6 (a)
Determine \[ [(p\Rightarrow q)\wedge q]\Rightarrow \neg p \] is a tautology.

4 M

6 (b)
Define isomorphic graphs. Show that following graphs are isomorphic

8 M

6 (c)
R be a relation on set of integers Z defined by

R={(x,y)|x-y is divisible by 3}

Show that R is an equivalence relation and describe the equivalence classes.

R={(x,y)|x-y is divisible by 3}

Show that R is an equivalence relation and describe the equivalence classes.

8 M

More question papers from Discrete Structures