Attempt all the questions.Each question carries equal marks. Parts of a question must be answered together.

Q1. Show that the necessary condition for a simple connected graph to be planar is e ≤ 3n - 6 where e and n denote total number of edges and vertices of the graph respectively.

Q2. Solve the following recurrence using Master theorem method:

T(n) = 4 T(n/2) + n2

Q3. Describe CONVOLUTION of two numeric functions with suitable example.

Q4. Show that the following premises are inconsistent:

(a) If Jack misses many classes through illness ,then he fails high school.
(b) If Jack fails high school ,then he is uneducated.
(c) If Jack reads a lot of books ,then he is not uneducated.
(d) Jack misses many classes through illness and reads a lot of books.

Q5. Solve the following recurrence:ar = ( ar-1 )7 / ( ar-2 )12 , a0 = 1 , a1 = 2

Q6. Prove that a graph with n vertices and n - 1 edges and no circuit is connected or prove that a tree is a connected graph.

Q7. If a simple graph has vertices ,find the maximum and minimum number of edges  in that graph. Q8.Prove that in a tree with two or more vertices ,there are at least two pendant vertices (leaves).

Q9. Determine an equivalent numeric function of the generating function A(Z) = 1 / ( 1- 4Z2 ).

Q10. Let f(n) = 2n2 + 5n + 5. Express f(n) in Big oh notation .Also find the necessary constants.

Q11. What do you mean by chromatic number of a graph ? Explain with a suitable example.

Q12. Use Kruskal's algorithm to determine a minimal spanning tree of the following connected weighted graph:

Q13. Check the validity of the following arguments:

All intelligent persons are Engineers.

John is not an Engineer.

Therefore, John is not intelligent.

Q14. How many people among 200,000 people are born at the same time ( hour, minute ,seconds) ?

Q15. Use mathematical induction to show that  n! ≥ 2n-1  , n = 1 ,2 ,3,......