Motivation. The three-dimensional cube can be formalized by $\mathcal P(\{0,1,2\})$ where vertices $x,y\in\mathcal P(\{0,1,2\})$ are connected by an edge if and only if their symmetric difference $x\mathbin\Delta y := (x\setminus y) \cup (y\setminus x)$ contains exactly $1$ element. If we want to assign to each vertex one of the colors black and white such that no two vertices connected by an edge get the same color, we use the concept of parity: color any vertices containing an even number of elements black, and the rest white. This "parity algorithm" works for any $\mathcal P(X)$ where $X$ is a finite set. But what happens in the infinite case?
Formal version. Consider the following statement:
(Parity principle:) If $X\neq \emptyset$ is a set, then there is $\mathcal B\subseteq \mathcal P(X)$ such that whenever $a,b\in \mathcal P(X)$ with $a\mathbin\Delta b = \{x\}$ for some $x\in X$, then $\mathcal B$ contains exactly one of $a$, $b$.
The Parity Principle is a theorem in $(\textsf{ZFC})$. Does the Parity Principle imply the Axiom of Choice in $(\textsf{ZF})$?
Best Answer
The Parity Principle follows from the axiom $\mathbf C_2$ (defined below) which is weaker than the Axiom of Choice. I don't know whether the Parity Principle implies $\mathbf C_2$, but that's another question.
For $n\ge2$ let $\mathbf C_n$ denote Mostowski's axiom of choice for $n$-element sets, which says that every collection of $n$-element sets has a choice function; see Andrzej Mostowski, Axiom of choice for finite sets, Fund. Math. 33 (1945), 137-168, and John Truss, Finite axioms of choice, Ann. Math. Logic 6 (1973), 147-176. These axioms $\mathbf C_n$ are weaker than the full Axiom of Choice; indeed, $\mathbf C_2$ does not even imply $\mathbf C_3$ (although $\mathbf C_2$ is equivalent to $\mathbf C_4$) in ZF.
Inasmuch as the hypercube graph contains no odd cycles, it will suffice to prove the following:
Theorem (ZF). The axiom $\mathbf C_2$ is equivalent to the assertion that every (finite or infinite) graph with no odd cycles is $2$-colorable.
Proof. First, suppose $\mathbf C_2$ holds, and consider a graph with no odd cycles. Note that each connected component admits exactly two proper blue/red $2$-colorings. Choose a proper $2$-coloring for each component and take the union to get a proper $2$-coloring of the whole graph.
Conversely, suppose that every graph with no odd cycles is $2$-colorable. In particular, every $1$-regular graph (matching) is $2$-colorable, and the assertion that every matching is $2$-colorable is plainly equivalent to the assertion that every collection of disjoint $2$-element sets has a choice function, which is equivalent to $\mathbf C_2$.