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?



Existence of Spanning Tree implies Well Ordering Principle
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).$


