If a connected graph has a unique spanning tree, then it is a tree.

Question

Prove if a connected graph has a unique spanning tree, then it is a tree.

Edit: This can be shown with proof by contradiction.

Answer 1

Suppose $G$ has a unique spanning tree $T$. For contradiction, assume that $G$ is not a tree. Then $G$ has an edge $e = uv$ not contained in $T$. Since $T$ spans $G$, there is a $u,v$-path $P$ in $T$. Then $P + e$ is a cycle in $G$. Form the tree $T'$ by starting with $T$, adding the edge $e$, and deleting one edge in $P$. You can verify that $T'$ is a spanning tree that is different from $T$:

1) It is connected because $P+e$ is a cycle and no edge in a cycle is a cut-edge.

2) It is acyclic because adding $e$ created exactly one cycle, and removing an edge from $P$ removed that cycle.

This is a contradiction, so $G$ must be a tree.

Answer 2

Well let me begin by saying the following proof is not pretty.

Let $G$ be a connected graph such that it has only one spanning tree, $T$. Suppose there is a pair of vertices $u$ and $v$ such that there are two distinct paths, $P_1$ and $P_2$, between them. Now it is possible to begin with one of these paths and create a tree. Start with a path, $P_1$. Let $L_1$ be the set of neighbours of vertices in $p_1$. Connect them with one edge to the path. Let $L_2$ be the set of neighbours of $L_1$. Connect the vertices in $L_2$ to those in $L_1$ using exactly edge. Continue the process until all vertices of $G$ are exhausted. The resulting graph is connected and the number of edges in it is one less than the number of vertices. Hence it is a tree. This construction is always possible since $G$ is connected. But we can create a distinct tree starting with $P_2$ which would mean there are two spanning trees of $G$ contradicting the assumption that there cannot be two distinct paths between any two vertices in $G$. Hence there can be only a unique path between any two vertices in $G$. There are such paths between all pairs since $G$ is connected. And hence $G$ is a tree.

Answer 3

$\def\P{\mathscr{P}}$ $\def\C{\mathscr{C}}$ A warning: this is a very detailed answer. The crux of the answer is that any subtree of a graph can be extended to a spanning tree by Zorn's Lemma. Then, if there is a unique spanning tree of a graph $F$, we can't have an edge not contained in that tree.

Let $G$ be a connected graph. Let $T$ be a subgraph of $G$ that is a tree. We claim that there is a spanning tree of $G$ that contains $T$.

Let $\P$ be the poset of all subtrees of $G$ that contain $T$ ordered by graph inclusion. Then, $\P$ is non-empty, as it contains $T$. Let $\C$ be a chain in $\P$. We construct a subgraph $T_{\C}$ of $G$ as follows:

The set of vertices of $T_{\C}$ is the set of vertices in $G$ that are vertices in one of the subgraphs in $\C$. Similarly, the set of edges of $T_{\C}$ is the set of edges in $G$ that appear as edges in one of the subgraphs in $\C$. You can think of $T_{\C}$ as the union of all the subgraphs appearing in $\C$.

$T_{\C}$ is a subgraph of $G$ because if $e$ is an edge in $T_{\C}$, then $e$ is an edge in some $T' \in \C$ and hence the two vertices of $e$ are vertices in $T'$ are and hence included in the set of vertices of $T_{\C}$. We also note that $T_{\C}$ contains as subgraphs all of the elements of $\C$. Hence, in particular, $T_{\C}$ contains $T$. Finally, we will show $T_{\C}$ is a tree. Suppose there is a cycle $e_{1}\cdots e_{n}$ in $T_{\C}$. Then, each of the edges must be in some $T_{i} \in \C$ and since there are only finitely many of them, there must be some $j$ such that $T_{j}$ contains all the other $T_{i}$. But then $e_{1}\cdots e_{n}$ is a cycle in the tree $T_{j}$, a contradiction. Hence, $T_{\C}$ is a tree.

The above paragraph shows that $T_{\C}$ is an upper bound for the chain $\C$ in $\P.$ So, we can apply Zorn's Lemma to get a maximal element $S$ in $\P$. We claim that $S$ is a spanning tree. Suppose it is not. Then, there is some vertex $x$ of $G$ that is not a vertex of $S$. Additionally, as $G$ is connected, we can choose $x$ to be a vertex such that there is a vertex $y \in S$ with an edge $e$ between $x$ and $y$. This is because we can always choose a path (composition of edges) from $x$ to a vertex of $S$.

Now, add $x$ and the edge $e$ to $S$ . Then, we get a new graph $S'$ that contains $S$ and does not have any cycles. This is because if there were a cycle in $S'$, it would have to contain the edge $e$ but there is no other edge containing $x$. Hence, $S'$ is in $\P$ and contains $S$ which contradicts the maximality of $S$. Thus, $S$ is a spanning tree. As it contains $T$, we have shown that every subtree of $G$ can be extended to a spanning tree.

After this rather long explanation, the proof of the problem is nice and short. Let $G$ be a connected graph with only one spanning tree. Suppose for contradiction that $G$ is not a tree. Then, there is some edge $e$ not contained in the unique spanning tree $T$. But $e$ is itself a tree and can be extended by the above argument to a spanning tree, which obviously cannot be $T$. This contradicts the uniqueness of $T$ as a spanning tree of $G$. Hence, $G$ is a tree.