10

11

12

13

14

a)

b)

a)

E7131

Consider the tree T, given below

Label the vertices of T appropriately and find the center and diameter of T

Prove the statement:

Every cut-set in a connected graph G must also contain at least one branch of
every spanning tree of G

List down the properties stating the relationship between the edges of graph G
and its dual G*

PART D
Answer any two full questions, each carries 9 marks.
Define spanning trees. Consider the graph G given below and obtain any three
spanning trees from G. Calculate the number of distinct spanning trees possible
from a complete graph with n vertices.

Let G =(V,E) be a connected graph, and let ಎ (५, 5) be a spanning tree of G.

Let e = (a, 0) be an edge of G not in T. Prove that, for any edge f on the path from a to b
in T, (V, (SU{e}) —{f}) is another spanning tree for 6

Define cut set. Find any four cut sets from the graph G given below and also find
the edge connectivity of G.

Define vertex connectivity and draw a graph with an articulation point.
State Euler’s Theorem (formula).

Draw two Kuratowski’s graphs and also prove that Kuratowsk’s first graph is
non planar using appropriate inequality.

Draw the geometric dual (G*) of the graph G given below and also check
whether ೮ and G* are self dual or not, substantiate your answer clearly?

Page 2 of 3

(3)

(3)

(3)

(5)

(4)

(5)

(3)
(1)

(4)
(5)