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.

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$?

share|improve this question

2 Answers 2

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.

share|improve this answer
    
but didn't we agree that the family is ordered by inclusion? –  Ronald May 13 '13 at 13:35
1  
As required by Zorn, the family is partially ordered by inclusion and we need that each totally ordered subset (chain) has an upper bound. –  Hagen von Eitzen May 13 '13 at 13:41
1  
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. –  Amudhan May 13 '13 at 13:42
    
ok! i thought the inclusion implies totally ordered set. But also why "both the paths will be contained in some $T_α$"? –  Ronald May 13 '13 at 13:53
1  
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. –  Amudhan 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.

share|improve this answer

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.