In using the Zorn's lemma to show that every connected graph contains a spanning tree, we let $\{T_{\lambda}: \lambda \in \Lambda \}$ be a family of trees contained in $X$ which is totally ordered by inclusion. But how to show that $\bigcup\limits_{\lambda \in \Lambda} T_\lambda$ is a also a tree in $X$?


Actually, $\bigcup\limits_{\lambda \in \Lambda} T_{\lambda}$ may not be a tree.

You have to show that every chain in your family of trees has an upper bound. So, given a chain $\{T_{\alpha}$| $\alpha \in A$}, take the union $T=\bigcup\limits_{\alpha \in A} T_{\alpha}$. It is straightforward to show that this is tree: you just have to show that, given any two vertices $v_1,v_2 \in T$, there is exactly one path between them.

(proof by contradiction: assume two paths - both the paths will be contained in some $T_{\alpha_0}$, but $T_{\alpha_0}$ is a tree, so you get a contradiction )

Now, since you have a poset where every chain has an upper bound, Zorn's lemma can be applied.

  • $\begingroup$ but didn't we agree that the family is ordered by inclusion? $\endgroup$ – Ronald May 13 '13 at 13:35
  • 1
    $\begingroup$ As required by Zorn, the family is partially ordered by inclusion and we need that each totally ordered subset (chain) has an upper bound. $\endgroup$ – Hagen von Eitzen May 13 '13 at 13:41
  • 1
    $\begingroup$ true, but that does not make the family a chain. A chain is a totally ordered set. You could have two trees in your family, which do not have any order between them. $\endgroup$ – user56914 May 13 '13 at 13:42
  • $\begingroup$ ok! i thought the inclusion implies totally ordered set. But also why "both the paths will be contained in some $T_α$"? $\endgroup$ – Ronald May 13 '13 at 13:53
  • 1
    $\begingroup$ both these paths have a start vertex and an end vertex, hence they are finite - since you're taking a union of a chain, eventually there will be a member which contains all the vertices in those paths. $\endgroup$ – user56914 May 13 '13 at 14:03

The argument here is one of the common arguments when using Zorn's lemma.

If $G$ is a graph which is not a tree then it has a finite subgraph which witnesses that.

  • If the chain was finite, then it has a maximal element. Therefore the union of the chain is that maximal element, and we are done. In fact we don't even care that the chain was finite, just that it had a maximal element.

  • If the chain doesn't have a maximal element, and the union is not a tree then there is a finite subset which witnesses that. But that finite subset must have been added somewhere along the way. This counterexample, if so appears in some $T_\lambda$ in our chain. But we assumed that all the $T_\lambda$ are trees, so that is impossible.

Note that this is the same argument that the increasing union of linearly independent sets is linearly independent; that the increasing union of filters is a filter; and that the increasing union of ideals is an ideal, etc. The key is if the union wasn't a such object, it would mean that somewhere along the union we added a counterexample -- which contradicts our assumptions.


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.