00000CS309121902

10 Sketch all spanning trees of the given graph (3)

11 Draw the two simplest non planar graphs and also mention their properties. (3)
PART D
Answer any two full questions, each carries 9 marks.
12 a) Define Spanning tree. Find any two spanning trees 11, T2 of the graph G given (6)

below. Also find the branch set, chord set, rank and nullity.

d

a

b :

b) Sketch two different binary trees on 13 vertices, one having maximum height and (3)
other having minimum height.
13 a) Define Cut set .Find all cutsets of the graph G given below and also find the edge (6)

connectivity of G.

e3 €9
‏به‎

oe

e4 e2

61

b) Define vertex connectivity and draw a graph with an articulation point. (3)