Question

Which connected simple graphs have exactly one spanning tree?

Short answer

The attached simple graph has entirely one spanning tree.

Step-by-step solution

Definition

An undirected graph within which there’s at the most one edge between each pair of vertices, and there are not any loops, which is a grip from a vertex to itself.

Graph has one spanning tree.

For this result consider the contrary. Let G is a simple connected graph that is not a tree and has a unique spanning tree T. Then there exists edge \({\bf{e = }}\left\{ {{\bf{u,v}}} \right\}\) in G that is not in T. As T is spanning, there is a path P between u, v in T, hence in G. Then \({\bf{P + e}}\) is a cycle in G.

Choose another edge \({{\bf{e}}_{\bf{1}}} \ne {\bf{e}}\) from P and construct \({{\bf{T}}_{\bf{1}}}\) where the edges are that in T with replacing e. As it turns out, \({{\bf{T}}_{\bf{1}}}\) is also connected and contains all the vertices of G. Hence another spanning tree of G, is a contradiction. Thus, our assumption is wrong.

Therefore, a connected simple graph has exactly one spanning tree.