Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I found a proof that every connected graph (possibly infinite) has a spanning tree in Diestel's Graph Theory (Fourth Edition), Ch. 8 that uses Zorn's Lemma, but at a crucial step it seems to be secretly assuming that there are only countably many vertices.

So I wondering:

Is it true that every connected graph has a spanning tree? If so, can it easily be proved using Zorn's Lemma (or Well Ordering Theorem or Axiom of Choice)?

Definitions, in the interest of making this question self contained: a graph is connected if every pair of vertices is joined by a finite path, a graph is a tree if it is connected and has no cycles, and a spanning tree of $G$ is a tree $T$ with vertex set $V(T)=V(G)$.

share|improve this question
1  
I would say that it is true and easily proved using Zorn's Lemma. Could you describe the step you think assumes countability, and elaborate on why you don't think it will work for uncountable graphs? –  Henning Makholm Oct 25 '11 at 22:25
1  
Where do you think that countability is being implicitly assumed? The union of a chain of trees is a tree, and a maximal tree is necessarily a spanning tree. –  Brian M. Scott Oct 25 '11 at 22:28
1  
It's not the case that the union of an ascending chain of trees has to be a spanning tree, even if G is countable. You get a spanning tree because you have a maximal tree. –  Chris Eagle Oct 25 '11 at 22:33
4  
@Matthew, Zorn's Lemma doesn't just give you an infinitely ascending chain. It gives you, in one step, a maximal element. And a maximal tree in G must span all of G -- if it didn't you could easily extend it to a larger tree, and therefore it wasn't maximal in the first place. –  Henning Makholm Oct 25 '11 at 22:33
2  
@Matthew: You should write an answer, then. It is a good question in my opinion. –  Asaf Karagila Oct 25 '11 at 22:44

1 Answer 1

up vote 8 down vote accepted

I figured out the answer and someone asked me to post it as an answer, so I am answering my own question in case this is helpful for anyone else.

Let $G$ be a connected graph and consider the set $S$ of all trees $T \subset G$ ordered by the subgraph relation. We wish to apply Zorn's lemma, so we must check first that every chain $\mathcal{C}$ has an upper bound, i.e. a tree containing every $T \in \mathcal{C}$ as a subgraph. We claim that $T^* = \cup \mathcal{C}$ is just such a tree.

Clearly $T$ a subgraph of $T^*$ for every $T \in \mathcal{C}$ by construction. The main thing is to check that $T^*$ is a tree. Suppose $T^*$ is not a tree. Then either $T^*$ is disconnected or it has a cycle. If $T^*$ is disconnected, then there are two vertices $u,v \in T^*$ which are not connected by a path in $T^*$. But $u \in T_u$ for some $T_u \in \mathcal{C}$ and $v \in T_v$ for some $T_v \in \mathcal{C}$ and $\mathcal{C}$ is a chain, so either $T_u \subset T_v$ or $T_v \subset T_u$ and in either case $u$ is connected to $v$ by a path in the larger tree, and $T^*$ in turn contains this path, a contradiction. The contradiction to $T^*$ containing a cycle is similar --- every edge in the cycle must appear somewhere in the chain, and then one of the supposed trees in the chain is not acyclic.

Every chain has an upper bound, so $S$ has a maximal element, by Zorn's lemma. It is easy to see that it must be a spanning tree.

share|improve this answer
    
If you want $T^{\ast}$ instead of $T\ast$, then use T^* or T^\ast. –  Srivatsan Oct 26 '11 at 0:36
5  
The existence of a spanning tree in an arbitrary graph is actually equivalent to the axiom of choice. –  Chris Godsil Oct 26 '11 at 1:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.