N A L A N D A O P E N U N I V E R S I T Y
Master of Computer Application Part-I
PAPER-VIII
(Advanced Discrete Mathematics)
Annual Examination, 2017
Time 3 Hours. Full Marks 80
Answer any Five Questions.
All questions carry equal marks.
1. Find the number of bijections on a set of n elements n 1.
2. Show that every non-negative integer can be written as a unique sum of distinct powers
of 2.
3. Solve the recurrence an 4an 2 where
a 0 a1 6
a 0 a 2 20
a1 a 2 20
4. Prove that
The sum of the degrees of all the vertices of any graph is even.
Any graph can only have an even number of odd vertices.
5. What is the difference between an Eulerian graph and an Eulerian circuit
6. Find all the graphs that have edge chromatic number 1.
Colour the edges of the graphs k 3 k 4 k 5 .
7. Construct a graph with chromatic number 5.
8. Let G be a graph each of whose vertices had degree k or k 1. If G has m vertices of
degree k and r vertices of degree k 1 then show that m 1)p 2q.
9. Show that C 6 is bipartite and K 3 is not bipartite.
10. Show that K 5 is not planar.