16
$\begingroup$

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

  • 2
    @Matthew: You should write an answer, then. It is a good question in my opinion.2011-10-25

1 Answers 1

12

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.

  • 6
    The existence of a spanning tree in an arbitrary graph is actually equivalent to the axiom of choice.2011-10-26