E E7131

Total Pages: 3
Reg No.: Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIFTH SEMESTER B.TECH DEGREE EXAMINATION, DECEMBER 2017

Course Code: CS309
Course Name: GRAPH THEORY AND COMBINATORICS (CS)
Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries3 marks. Marks
1 Consider a graph G with 4 vertices: v1, v2, v3 and v4 and the degrees of vertices (3)
are 3, 5, 2 and 1 respectively. Is it possible to construct such a graph G? If not,
why?
2 Draw a disconnected simple graph G1 with 10 vertices and 4 components and (3)
also calculate the maximum number of edges possible in G1.
3 State Dirac’s theorem for hamiltonicity and why it is not a necessary condition (3)
for a simple graph to have a Hamiltonian circuit.
4 Differentiate between symmetric and asymmetric digraphs with examples and (3)
draw a complete symmetric digraph of four vertices.
PART B

Answer any two full questions, each carries 9 marks.

5 9) What are the basic conditions to be satisfied for two graphs to be isomorphic? (6)
Are the two graphs below isomorphic? Explain with valid reasons

b) Write any two applications of graphs with sufficient explanation (3)
6 2) Consider the graph © given below: (4)

Define Euler graph. Is G an Euler? If yes, write an Euler line from G.
b) What is the necessary and sufficient condition for a graph to be Euler? And also (5)
prove it.
7 2) Define Hamiltonian circuits and paths with examples. Find out the number of (5)
edge-disjoint Hamiltonian circuits possible in a complete graph with five vertices
b) State Travelling-Salesman Problem and how 797 solution is related with (4)
Hamiltonian Circuits?

PART C
Answer all questions, each carries 3 marks.
8 List down any two properties of trees and also prove the theorem: A graph is 4 (3)
tree if and only if it is a minimally connected.

Page 1 of 3