10
11

12

b)

6

a)

a)

೧5905 Pages: 4

Define Hamiltonian circuit. Give an example. What general class of graphs is (4)
guaranteed to have a Hamiltonian circuit? Also draw a graph that has a
Hamiltonian path but not a Hamiltonian circuit.

Prove that if a connected graph G is decomposed into two subgraphs 81 and g2, (3)
there must be at least one vertex common between 81 and ഇ

PART C
Answer all questions, each carries 3 marks.
Prove that the distance between vertices of a connected graph is a metric. (3)
3 Find the eccentricity of all vertices in G given below and also mark (3)

the center of G

ರ =>
ii) Find the number of possible labelled trees that can be constructed
with 50 vertices.
Draw the two simplest non-planar graphs and also mention their properties. (3)

What is the necessary and sufficient condition for two graphs to be duals of each (3)
other? Prove.
PART 0
Answer any two full questions, each carries 9 marks.
Draw the geometric dual (G*) of G given and also write about the relationship (6)
between a planar graph G and its dual G*

Define rooted binary tree with an example (3)
Find the number of edges and vertices of a graph G if its rank and nullity are 6 (2)
and 8 respectively

Prove the statement,”Every circuit has an even number of edges in common with (4)
any cut-set”

Consider a binary tree with four weighted pendant vertices. Let their weights (3)
be0.5, 0.12, 0.3 and 0.11. Construct a binary tree with minimum weighted path

length.

Define cut sets with an example. Give an application of finding cut-sets or edge (4)

Page 2 of 4