Editing Spanning tree (section)

==In infinite graphs==
Every finite connected graph has a spanning tree. However, for infinite connected graphs, the existence of spanning trees is equivalent to the [[axiom of choice]]. An infinite graph is connected if each pair of its vertices forms the pair of endpoints of a finite path. As with finite graphs, a tree is a connected graph with no finite cycles, and a spanning tree can be defined either as a maximal acyclic set of edges or as a tree that contains every vertex.<ref name="serre" />

The trees within a graph may be partially ordered by their subgraph relation, and any infinite chain in this partial order has an upper bound (the union of the trees in the chain). [[Zorn's lemma]], one of many equivalent statements to the axiom of choice, requires that a partial order in which all chains are upper bounded have a maximal element; in the partial order on the trees of the graph, this maximal element must be a spanning tree. Therefore, if Zorn's lemma is assumed, every infinite connected graph has a spanning tree.<ref name="serre">{{citation|title=Trees|first=Jean-Pierre|last=Serre|author-link=Jean-Pierre Serre|page=23|publisher=Springer|series=Springer Monographs in Mathematics|year=2003}}.</ref>

In the other direction, given a [[family of sets]], it is possible to construct an infinite connected graph such that every spanning tree of the graph corresponds to a [[choice function]] of the family of sets. Therefore,
if every infinite connected graph has a spanning tree, then the axiom of choice is true.<ref>{{citation
 | last = Soukup | first = Lajos
 | contribution = Infinite combinatorics: from finite to infinite
 | doi = 10.1007/978-3-540-77200-2_10
 | location = Berlin
 | mr = 2432534
 | pages = 189–213
 | publisher = Springer
 | series = Bolyai Soc. Math. Stud.
 | title = Horizons of combinatorics
 | volume = 17
 | year = 2008| isbn = 978-3-540-77199-9
 }}. See in particular Theorem 2.1, [https://books.google.com/books?id=kIKW18ENfUMC&pg=PA192 pp.&nbsp;192–193].</ref>