Using the Well-Ordering Principle, which is equivalent to the Axiom of Choice, it can be proved that

(S): for every simple, undirected graph $G$, finite or infinite, either $G$ or its complement $\bar{G}$ is connected.

Does (S) imply (AC)?


(S) is a theorem of ZF.

Proof: Let $G$ be a graph, and let $v$ be a vertex of $G$. Define $$P_v = \{w \,:\, \text{there is a path from } v \text{ to } w\}.$$ If $P_v$ is the vertex set of $G$, then $G$ is connected. If not, then $\overline{G}$ (the complement of $G$) contains the complete bipartite graph on $P_v$ and $V(G) \setminus P_v$. But then it's easy to see that any two vertices in $\overline{G}$ are connected by a path of length $1$ or $2$.

  • 16
    $\begingroup$ For the record, this is the standard proof. $\endgroup$
    – Wojowu
    Apr 9 '18 at 13:42
  • $\begingroup$ Is this also a theorem in a weaker theory? I seem to recall that Pv or something like it is not definable in pure graph theory (say language with equality and one binary relation of adjacency between vertices)? Gerhard "Can't Get There From Here" Paseman, 2018.04.09. $\endgroup$ Apr 9 '18 at 17:11
  • 6
    $\begingroup$ @GerhardPaseman: The smart-aleck in me would like to point out that every theorem of ZF is a theorem of some weaker theory, namely the theory consisting of the (finitely many) axioms actually used in the proof. The sincere mathematician in me thinks you might be thinking of this: en.wikipedia.org/wiki/Logic_of_graphs#Examples_2. $\endgroup$
    – Will Brian
    Apr 9 '18 at 18:00
  • $\begingroup$ Forgive my ignorance, but what does ZF mean exactly? Its not referenced anywhere in this answer or in the question. $\endgroup$
    – user1447
    Apr 10 '18 at 6:28
  • $\begingroup$ @user1447: "ZF" stands for "the axioms of Zermelo-Fraenkel set theory" (see en.wikipedia.org/wiki/…). Saying "some statement (S) is equivalent to (AC)" means that using ZF, one can show that (S) implies (AC) and (AC) implies (S). $\endgroup$
    – Will Brian
    Apr 10 '18 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.