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

  • 1
    $\begingroup$ 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? $\endgroup$ Oct 25, 2011 at 22:25
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 25, 2011 at 22:28
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 25, 2011 at 22:33
  • 5
    $\begingroup$ @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. $\endgroup$ Oct 25, 2011 at 22:33
  • 2
    $\begingroup$ @Matthew: You should write an answer, then. It is a good question in my opinion. $\endgroup$
    – Asaf Karagila
    Oct 25, 2011 at 22:44

1 Answer 1


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.

  • $\begingroup$ If you want $T^{\ast}$ instead of $T\ast$, then use T^* or T^\ast. $\endgroup$
    – Srivatsan
    Oct 26, 2011 at 0:36
  • 7
    $\begingroup$ The existence of a spanning tree in an arbitrary graph is actually equivalent to the axiom of choice. $\endgroup$ Oct 26, 2011 at 1:49
  • $\begingroup$ I'm trying to prove that the maximal element is spanning. I'll post my proof and ask you if you know an alternative proof for the spanning property: For if it were not, there would be a vertex apart from the tree, which we can then connect to the tree with a path to one of its leaves (without creating a cycle), forming a bigger tree, contradicting the maximality. $\endgroup$
    – SK19
    Sep 8, 2019 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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