Reg No.:

06000CS309122001 Pages: 5

Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

Fifth Semester B.Tech Degree Regular and Supplementary Examination December 2020

Max. Marks: 100

2

3

4

5 ஐ
b)

6 a)
b)

Course Code: CS309

Course Name: GRAPH THEORY AND COMBINATORICS

PARTA
Answer all questions, each carries 3 marks.
Prove that the number of vertices of odd degree in a graph is always even.

11 children in a nursery school stand next to each other in circle such that they
have different friends each time. How much such different arrangements are

there? Justify your answer.

What is the number of vertices in an undirected connected graph with 27 edges,

6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?

Find the number of distinct hamiltonian cycles (not edge disjoint) possible in a

complete graph of n vertices, where n>=3.
PART 13
Answer any two full questions, each carries 9 marks.

If graph G has 8 vertices and it is Eulerarian (has Euler Circuit), then find the

maximum number of edges in the Graph G.

Prove that “A connected graph is Eulerian if and only if every vertex has even

degree”.
State and prove Dirac's theorem for hamiltonicity.

Consider an undirected graph G with 100 nodes. Find the minimum number of

edges to be included in G so that the graph G is guaranteed to be connected.

Page 1 5

Duration: 3 Hours

Marks

(3)

(3)

(3)

(3)

(4)

(5)

(5)

(4)