Question 10740 – Minimum-Spanning-Tree

What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?

Correct Answer: C

Question 11 Explanation:

If graph is connected and contains n vertices and n edges means there is possibility of only one cycle.
→ If we create a different spanning tree by removing one edge at a time.
→ For cycle required 3 minimum edges. So there is at least 3 spanning trees in such a graph.