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

I am confused about how to approach this. It says:

Show that every connected graph has a spanning tree. It's possible to find a proof that starts with the graph and works "down" towards the spanning tree.

I was told that a proof by contradiction may work, but I'm not seeing how to use it. Is there a visual, drawing-type of proof? I appreciate any tips or advice.

-
Here's a hint: Start with the graph, and keep throwing away extra "stuff" until you arrive at a spanning tree; you should maintain the connectedness of the graph throughout. I will leave you to figure out what "stuff" means. :) –  Srivatsan Apr 24 '12 at 13:59
@Srivatsan - Thank You So Much, I think it's getting clearer. –  Adel Apr 24 '12 at 14:15

## 3 Answers

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?

-
Thank You Very Much Srivatsan, this helps a lot. I am much clearer on it, so I'll spend some more time and I should get it soon. –  Adel Apr 24 '12 at 14:38

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\}\ .$$

-
Thanks so much Christian. Is "upwards" being used figuratively though? Actually the problem said to prove it in two ways, my partner in class is doing the "upwards" part . –  Adel Apr 24 '12 at 21:03
Does this proof invoke the axiom of choice "secretly" or maybe not so secretly? –  TylerHG Oct 1 at 5:48
@TylerHG: If the given graph is too large the axiom of choice might be needed. Consider the following example: Let $V:={\mathbb R}^2$ and connect two vertices by an edge iff their euclidean distance is $=1$. –  Christian Blatter Oct 1 at 8:06

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.)

-
Thank you very much Marcel! –  Adel Apr 25 '12 at 0:57