# Andhra University BE/B.Tech Discrete Mathematical Structures-I Previous Paper 2010

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 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 n^{3}+1>n^{2}+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 x _{1}=x_{2}=x_{3}=x_{4}=20 of 1<=x_{1}<=6, 1<=x_{2}<=7, 1<=x2<=8 and 1<=x_{4}<=9?.*

*(b) Consider (1+2x) ^{n} to prove*

* C(n,0)+2c(n,1)=2 ^{2}c(n,2)+…….+2^{n}c(n,n)=3^{n}.*

*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 F _{r}=2 F_{101}+f_{100}.*

*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 W_{8}.

( iii) A complete graph K_{n}

## Leave a Reply

You must be logged in to post a comment.