243 2 ಗಣ ~ ON os
‏بک‎ 20 டு
E 85905 പ്ല ९ REFERENRABeS: Ye:

இட a

Reg No.: Name:

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

Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries 3 marks. Marks
] Prove that the number of vertices of odd degree in a graph is always even (3)
2 Show that in a simple graph with n vertices, the maximum number of edges is (3)
n(n-1)/2 and the maximum degree of any vertex is 1-1.
3 Differentiate between complete symmetric and complete asymmetric graph with (3)
an example each.
4 State Dirac’s Theorem and check its applicability in the following graph, G (3)
PART B

Answer any two full questions, each carries9 marks.

5 2) Define isomorphism between graphs? Are the two graphs below isomorphic? (5)

Justify
^ ۸۷
B D ۷ ><
A 5 U Y
b) Consider a complete graph G with 11 vertices. (4)

1. Find the maximum number of edges possible in G.
2. Find the number of edge-disjoint Hamiltonian circuits in G.
6 8 Aconnected graph G is an Euler graph if and only if all vertices of G are ofeven (6)
degree.Prove the statement.

b) There are 37 telephones in the city of Istanbul, Turkey. Is it possible to connect (3)
them with wires so that each telephone is connected with exactly 7
others?Substantiate your answer with graph concepts.

7 9) Give any two applications of graphs. Explain. (2)

Page 1 of 4