# Existence of Spanning Tree implies Well Ordering Principle

1. Every connected graph has a spanning tree.
2. Every non-empty set can be well ordered.

Basically I am trying to show that statement 1 implies statement 2. What I tried is as following: Let $X \ne \emptyset$, define a graph $G$ with $$V(G) := \{v_{S}:S \subseteq X\}$$ and $v_S v_T \in E(G)$ if and only if either $S \subseteq T$ and $|T| = |S| + 1$ or vice versa. By statement 1, there is a spanning tree so we choose the path (possibly infinite) that connects $v_{\emptyset}$ and $V_X$, and define a total order $\le$ on $X$ by the order each element $x \in X$ is added in the path that connects $v_{\emptyset}$ and $v_X$.

I talked to a professor about this, apparently connected means each pair of vertices is connected by a FINITE path, so my proof is technically wrong, but I think that's the general direction to proceed. Any hint on actually proving it?

• This is a good question, just not for this site - you should ask it at math.stackexchange. Jan 16, 2016 at 6:06
• As the well-ordering principle is equivalent to the axiom of choice, forget about well-ordering and just prove directly that (1) implies AC. Let $A_i,i\in I$ be a given family of nonempty sets. Let $A=\bigcup_{i\in I}A_i$. Assume w.l.o.g. that $I\cap A=\emptyset.$ Let $G=(V,E)$ where $V=I\cup A$ and $$E=\{\{u,v\}:u,v\in A,u\ne v\}\cup\{\{i,v\}:i\in I,v\in A_i\}.$$Let $T$ be a spanning tree for this connected graph. Choose $a\in A.$ For each $i\in I$ the tree $T$ contains a unique path $P_i$ from $i$ to $a,$ and $P_i$ contains a unique edge $\{i,v_i\}$ where $v_i\in A_i.$
– bof
Jan 16, 2016 at 6:37
• Note also that a well-order is very different from a total order. I do not know whether "every set can be totally ordered implies the axiom of choice. Jan 16, 2016 at 6:43
• See theorem 2. Jan 16, 2016 at 7:40
• I think the question is on-topic for MO, and that @bof's comment should be an answer. I have voted to re-open. Jan 16, 2016 at 15:39

Let AC denote the axiom of choice. The proof of the implication AC $\implies$ (2) is somewhat nontrivial. Inasmuch as the equivalence AC $\iff$ (1) is quite trivial, it seems unlikely that any "direct" proof of the implication (1) $\implies$ (2) will be much simpler than (1) $\implies$ AC $\implies$ (2). The rest of this answer is devoted to exhibiting simple proofs of AC $\implies$ (1) and (1) $\implies$ AC.
AC $\implies$ (1): Let $G=(V,E)$ be a connected graph. Choose a vertex $r\in V.$ For each vertex $v\in V\setminus\{r\},$ choose a vertex $v'\in V$ such that $v'$ is adjacent to $v$ and $d(v',r)\lt d(v,r).$ The set of all edges $\{v,v'\}$ is a spanning tree.
(1) $\implies$ AC: Let $A_i (i\in I)$ be a family of nonempty sets, and let $A=\bigcup_{i\in I}A_i.$ We may assume that $I\cap A=\emptyset.$ Consider the connected graph $G=(V,E)$ where $V=I\cup A$ and $$E=\{\{u,v\}:u,v\in A,u\ne v\}\cup\{\{i,v\}:i\in I,v\in A_i\}.$$ Let $T$ be a spanning tree for $G$. Choose a vertex $r\in A.$ For each $i\in I$ the tree $T$ contains a unique path $P_i$ from $i$ to $r,$ and $P_i$ contains a unique edge $\{i,a_i\}$ where $a_i\in A_i.$ Now $i\mapsto a_i$ is a choice function for the family $A_i (i\in I).$