# Prove graph cannot have exactly two distinct spanning trees [closed]

Prove that a graph cannot have EXACTLY two distinct spanning trees.

• Welcome to MSE! Users are more likely to offer aid if you provide evidence that you have made an attempt in good faith to solve the problem by yourself. In addition, we can offer more targeted aid if you specify previous attempts you have made, as then we may be able to identify where you are struggling. For more on how to ask questions on this site, please visit math.stackexchange.com/help/asking. Commented Mar 20, 2015 at 6:11

The union of the two spanning trees contains a cycle (contains too many edges to be a tree), cycles have length greater than $2$. Removing any edge from a cycle leaves a connected graph, so the union of the two spanning trees has at least $3$ spanning trees, each of which is a spanning tree for the original graph.
• I think your exposition is a little bit too terse. Call the edges of the cycle $e_1,e_2,\dots,e_n.$ It's not enough to say that $G-e_i$ is connectred and therefore has a spanning tree $T_i,$ because the trees $T_i$ are not necessarily distinct. It would be clearer to say that there is a spanning tree $T_i$ which omits the edge $e_i$ but contains the edges $e_j$ for $j\ne i.$