8
$\begingroup$

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.

  • 0
    @Srivatsan - Thank You So Much, I think it's getting clearer.2012-04-24

4 Answers 4

6

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?

  • 0
    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.2012-04-24
5

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

  • 1
    @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$.2015-10-01
3

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

  • 0
    Thank you very much Marcel!2012-04-25
0

Let G be a simple connected graph, if G has no cycle, then G is the spaning tree of itself. If G has cycles, remove one edge from each cycle,the resulting graph will be a spanning tree.