How many Spanning Trees are possible from the graph given below?
(a) 24
(b) 34
(c) 44
(d) 54
Explain ---->
total 9 edges and 6 vertices..
for spanning tree we need 6 vertices and 5 edges..
no of graphs with 5 edges : 9C5
no of graph with 3 length cycle (may be disconnected) = select any cycle of length 3 (select any small triangle) and then out of 6 vertices select any 2..
= (6C2)*3 + 12(for middle triangle) = 57
find no of 4 length cycle = select 4 length cycle and for rest 1 edge select those edges which doesn't produces 3 length cycle..
= 4 + 4 + 4 = 12
no of 5 length cycle = 3
total spanning tree = 126 - (57 + 12 + 3)
= 126 - 72
= 54
for spanning tree we need 6 vertices and 5 edges..
no of graphs with 5 edges : 9C5
no of graph with 3 length cycle (may be disconnected) = select any cycle of length 3 (select any small triangle) and then out of 6 vertices select any 2..
= (6C2)*3 + 12(for middle triangle) = 57
find no of 4 length cycle = select 4 length cycle and for rest 1 edge select those edges which doesn't produces 3 length cycle..
= 4 + 4 + 4 = 12
no of 5 length cycle = 3
total spanning tree = 126 - (57 + 12 + 3)
= 126 - 72
= 54
No comments:
Post a Comment