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

well-orderis very different from atotal order. I do not know whether "every set can be totally ordered implies the axiom of choice. $\endgroup$10more comments