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

up vote 25 down vote accepted

(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$.

  • 15
    For the record, this is the standard proof. – Wojowu Apr 9 at 13:42
  • 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. – Gerhard Paseman Apr 9 at 17:11
  • 5
    @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. – Will Brian Apr 9 at 18:00
  • Forgive my ignorance, but what does ZF mean exactly? Its not referenced anywhere in this answer or in the question. – user1447 Apr 10 at 6:28
  • @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). – Will Brian Apr 10 at 10:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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