: 0000 02 Pages: 5

Reg No.: Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
Fifth semester B.Tech degree examinations (S) September 2020

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 pendent vertex, isolated vertex and null graph with an example. (3)
2 Show that in a simple graph with n vertices ,the maximum number of edges is n(n- (3)
1)/2
3 DefineHamiltonian circuitsand path with examples.Find out the number of edge (3)

disjoint Hamiltonian circuits possible in a complete graph with five vertices.
4 State and prove Dirac’s Theorem of Hamiltonicity. (3)

PART ‏جا‎
‎Answer any two full questions, each carries 9 marks.

5 9) _ Define subgraphs.What are edge disjoint and vertex disjoint subgraphs? Construct (4)

two edge disjoint subgraphs of the graph G.