Question

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) 4

I have been asked this question in semester exam.

This question is from Spanning Trees in portion Trees of Discrete Mathematics

Answer 1

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.