What is the largest integer m such that every simple connected graph with n vertices and m edges contains at least 2 different spanning trees? A. 1 B. 2 C. 3 D. n

GATE 2007 · Discrete Mathematics · Graph Connectivity · medium

Answer: 3

1. Check m = n-1 (tree case): For m = n-1, any connected graph with n-1 edges must be a tree (acyclic). A tree has exactly 1 spanning tree: itself. So m = n-1 does NOT guarantee at least 2 spanning trees -- it fails for tree graphs.
2. Check m = n (unicyclic case) and conclude: For m = n, the graph has one extra edge beyond a spanning tree, creating exactly one cycle of length g >= 3 (simple graph, no multi-edges). Number of spanning trees = g >= 3 >= 2. All connected simple graphs with m = n edges have at least 3 spanning trees. The largest constant m (a fixed integer) that guarantees this is C = 3, the minimum possible cycle length.