E E192047 Pages:4

even degree.

7 ഒ) State travelling salesman problem and how TSP solution is related to Hamiltonian (5)
circuits.
b) State and Prove Dirac’s Theorem for Hamiltonicity. (4)
PART ^
Answer all questions, each carries3 marks.
8 Prove that the distance between the vertices of a connected graph is a metric (3)
9 List down any two properties of a tree and also prove the following theorem: A graph (3)

is a tree if and only if it is minimally connected.

10 Define the terms vertex connectivity and edge connectivity with examples. (3)
11 Give the different representations of a planar graph. (3)
PART 0

Answer any two full questions, each carries9 marks.
12 a) Find the eccentricity of all vertices in the graph G given below and also mark the (6)

center, radius and diameter of G

3 b
€ e
f 8
b) State and prove Cayley’s theorem (3)
13 லி Find the Geometrical dual (G*) of the graph G given below (5)

b) List out the properties stating the relationship between the graph G and its dual G* (4)