Show that a simple connected graph G contains a cycle if and only if it contains more than one spanning tree.

Question

This doesn't seem like a huge leap to prove this statement. However, I'm having trouble writing out a proof formally. I understand that I need to prove two directions. Thanks for your help

Answer 1

A spanning tree embeds paths between each pair of vertices and has $n-1$ edges where the graph $G$ has $n$ vertices.

Another useful property is that every subtree of a graph can be extended to a spanning tree.

If two spanning trees exists and are distinct they must have some edges which are not in common. Say edge $A-B$ is not on the first tree, but only in the second.

If you add that edge to the first tree you get a graph with $n$ vertices and $n$ edges, which thus can't be a tree, and thus has a cycle.

On the other side, if there is a cycle, it has at least $3$ vertices $A-B-C$ ($C$ may be connected again with $A$ or with some other vertex, it does not matter). What matters is that the cycle contains at least two adjacent edges, here $A-B$ and $B-C$ and you can delete any of them and the graph is still connected.

So, you first delete $A-B$ and consider the subtree made of the edge $B-C$ only. You know that you can extend this to a spanning tree that will contain $B-C$.

You do the same reversing the roles, i.e. you delete $B-C$ and you construct a spanning tree as an extension of the "tree" made only of the edge $A-B$.

So you have constructed two trees which are distinct because there is an edge which appears in one of them but not in the other.

Answer 2

=>

It's obviously, because if there is a cycle, then there are at least 2 spanning trees with different direction.

<=

There are at least $n-1$ edges , but because of there are two, or more spanning trees, so there are at least $n$ edges. In connected graph with $n$, or more edges exist one, or more cycle (because if there are no cycles this graph is tree, but there are at least $n$ edges).