06000CS309122001

b) Define distance between the vertices d(v,u) of a connected graph G. Prove that (5)

the distance function of a connected graph is a metric.

13 9) Define vertex and edge connectivity. Explain any one application showing the (4)

relevance of vertex and edge connectivity.

b) Define distance between two spanning trees of a graph. Draw any two spanning (5)

trees of the below graph such that the distance between them is >=3.

14 a) Define a fundamental cut-set of a graph. Find all the fundamental cut-set of the (5)

graph below with respect to a spanning tree.

b

b) Draw the geometric dual of the graph G shown below (4)

PART 17
Answer any four full questions, each carries 10 marks.

15 Consider the below graph. Find a spanning tree. Find the fundamental circuit (10)

matrix and fundamental cutset matrix with respect to the spanning tree.

Page 3 of 5