Skip to main content
1 of 3
bof
  • 13.4k
  • 2
  • 43
  • 66

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 $v_0\in V.$ For each vertex $v\in V\setminus\{v_0\},$ choose a vertex $v'\in V$ so that $v'$ is adjacent to $v$ and $d(v',w)\lt d(v,w).$ 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 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 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.$ Now $i\mapsto v_i$ is a choice function for the family $A_i (i\in I).$

bof
  • 13.4k
  • 2
  • 43
  • 66