1.

For every spanning tree with n vertices and n edges what is the least number of different Spanning trees can be formed?(a) 2(b) 5(c) 3(d) 4I have been asked this question in semester exam.This question is from Spanning Trees in portion Trees of Discrete Mathematics

Answer»

Correct option is (c) 3

Easiest explanation: If GRAPH is CONNECTED and has ‘n’ edges, there will be EXACTLY one cycle, if n vertices are there. A different spanning TREE can be constructed by removing one edge from the cycle, one at a time. The minimum cycle length can be 3. So, there MUST be at least 3 spanning trees in any such Graph. Consider a Graph with n = 4, then 3 spanning trees possible at maximum (removing edges of cycle one at a time, alternatively). So, any Graph with minimum cycle length ‘3’ will have at least 3 spanning trees.


Discussion

No Comment Found

Related InterviewSolutions