E E5840 Pages: 3
Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIFTH SEMESTER B.TECH DEGREE EXAMINATION, APRIL 2018
Course Code: CS309
Course Name: GRAPH THEORY AND COMBINATORICS

Max. Marks: 100 Duration: 3 Hours
PARTA
Answer all questions, each carries 3 marks Marks
1 Define isomorphism between two graphs. Are the following graphs are isomorphic (3)

to each other? Justify your answer.

ریم
ک ہے
‎For the following graph, find the shortest path between 17013111 to v4. Also finda (3)‏ 2
‎Euler circuit.‏

v2
vl

3 Define the following with example. (3)

i) Isomorphic digraph ii) Complete symmetric digraph
4 Define Hamiltonian graph.Find an example of a non-Hamiltonian graph with a (3)

Hamiltonian path.
PART B

Answer any two full questions, each carries 9 marks

5 9) Fora Eulerian graph ©, prove the following properties. (6)

i) The degree of each vertex of G 15 even. 11) © 15 an edge-disjoint union of cycles.

b) Discuss the Konigsberg Bridge problem.Is there any solution to the problem? (3)
Justify your answer.

6 93) Prove that a simple graph with n vertices must be connected, if it has more than (6)

(n-1)(n-2)/2 edges.

b) 19 students in a nursery school play a game each day, where they hold hands to (3)
form a circle. For how many days can they do this, with no students holding hands
with the same playmates more than once? Substantiate your answer with graph
theoretic concepts.

Page 1 of 3