10
$\begingroup$

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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
27
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 16
    $\begingroup$ For the record, this is the standard proof. $\endgroup$
    – Wojowu
    Commented Apr 9, 2018 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$
    – Gerhard Paseman
    Commented Apr 9, 2018 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
    Commented Apr 9, 2018 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
    Commented Apr 10, 2018 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
    Commented Apr 10, 2018 at 10:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .