How to show that every connected graph has a spanning tree, working from the graph "down"

Here is how I think of the problem. This is just an approach, not a complete solution.

A graph could fail to be a tree for two distinct reasons:

• ("The graph has too few edges.") It is disconnected; i.e., some two vertices of the graph cannot be reached using the graph edges alone.

• ("The graph has too many edges.") It contains a cycle.

Warning: The sentences in italics are just for the sake of intuition, and should not be taken literally. For instance, as an easy exercise, contruct a graph such that (i) it has at least one cycle; and (ii) it is disconnected. If one takes the italicised sentences literally, one would be forced to conclude that this graph has too few and too many edges, simultaneously.

In your case, you are given a connected graph $G$. So if at all $G$ is not a tree, it is because it contains redundant edges, in the form of cycles. Thus we may want to "trim" the graph by deleting unnecessary edges. Of course, while doing so, we would like to ensure that we don't destroy the connectedness of the graph. The real question then is: what edge(s) would you pick to delete?

Does this help you? Or do you want more hints?

Work "upwards" instead of "downwards". Choose a vertex $v_0$ and put $V_0:=\{v_0\}$, $E_0:=\emptyset$. Then proceed recursively as follows (it's pretty obvious):

Assume that for some $k\geq0$ a partial tree $(V_k, E_k)$ has been constructed and that $V':=V\setminus V_k$ is not empty. Then let $V''=\{v_1,\ldots, v_m\}$ be the set of vertices $v\in V'$ such that $\{v,w\}\in E$ for some $w\in V_k$. For each $v_j\in V''$ choose a $w_j\in V_k$ and put $$V_{k+1}:=V_k\cup V''\ , \quad E_{k+1}:=E_k\cup\bigl\{\{v_j,w_j\}\bigm|1\leq j\leq m\bigr\}\ .$$

The essence of what you're getting at is the equivalence of these definitions:

Definition 1:

A spanning tree of a connected graph $G$ is subtree $T$ of $G$ for which every vertex of $G$ is incident to an edge of $T$.

Definition 2:

A spanning tree of a connected graph $G$ is a maximal set of edges containing no cycles.

Actually there is a third equivalent definition, sort of combining the two ideas above:

Definition 3.

A spanning tree of a connected graph $G$ is a minimal set of edges containing all vertices.

Once you understand these equivalences (the proofs are better discovered than read), it will become clear how to show every graph has a spanning tree in both ways: building up using Def. 2, and building down using Def. 1. Indeed in either case the proof will jump out at you!

If you're really stuck here's an outline of the equivalence of the two definitions: suppose you have a spanning tree in the second sense. Could it be disconnected? (No. Why?) Could it be missing a vertex? (No. Why? You could add an edge.)

Suppose you have a spanning tree in the first sense, clearly it has no cycles, but could you add any edge to it? (No. Why? You'd create a cycle.)