E E192047 Pages:4

Reg No.:_ Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
V SEMESTER B.TECH DEGREE EXAMINATION(R&S), DECEMBER 2019
Course Code: CS309
Course Name: GRAPH THEORY AND COMBINATORICS

Max. Marks: 100 Duration: 3 Hours
PARTA
Answer all questions, each carries3 marks. Marks
1 Define the terms a) Walk b) Path and c) Circuit with an example. (3)
2 Prove that the no of vertices of odd degree in a graph is always even (3)
3 Draw a graph that has a Hamiltonian path but does not have a Hamiltonian circuit. (3)
4 Differentiate between Symmetric and Asymmetric digraphs with examples and draw a (3)

complete symmetric digraph of four vertices.
PART ‏تا‎
‎Answer any two full questions, each carries9 marks.

5 9) Prove that a simple graph with n vertices and k components can have at most (n-k)(n- (4)
k+1)/2 edges
b) Define Isomorphism of graphs. Check whether the two graphs are isomorphic or not (5)

G छा

6 a) Define Euler graph. Check whether the graph is an euler graph or not. If yes, give the (5)

Euler line and justify your answer.

b) Prove that a connected graph G is an Euler graph if and only if all vertices of G are of (4)