Existence of Spanning Tree implies Well Ordering Principle 
*

*Every connected graph has a spanning tree.

*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?
 A: 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).$
