Thread: (Graph Theory)Prove that graph X is a tree.

Let X be a graph with ONLY one spanning tree. Prove that X is a tree.

What I proved so far is that X is connected since all graphs with a spanning tree should be connected. All I need to do now is to prove that it's acyclic or has n-1 edges.

Any leads?

I propose this steps to prove the contraposition (it's not a complete proof, i let you fill the blank and formalize it all) :

We suppose X isn't a tree (i.e. has at least one cycle).
If X isn't connected, it's done (no spanning tree). So we assume that X is connected and choose a spanning tree.

At least one edge of the cycle isn't an edge of the spanning tree.

(1) Adding this edge produces at most one cycle. (I think it's even exactly one cycle, i let you prove that.)

(2) Once this edge E added, let V and V' be the vertices of E. We know (by (1)) that E is involved in a cycle, so are V and V'.
Removing one of the edges (other than E) adjacent to V or V' and involved in the cycle, we have a spanning tree. (It's clear that the number of edges is n-1, so you just have to prove that it's still connected.)

(3) We found two spanning tree : done !


(We just proved the contraposition of your lemma, so your lemma too.)

I hope it helps.

--
Pece