## Any graph or its complement is connected

This is a short note of something that I wasn’t sure whether it is true for infinite graphs. Let $G = (V,E)$ be any simple, undirected graph, finite or infinite, such that $V \neq \emptyset$. By $\bar{G}$ we denote the complement of $G$.

Proposition. At least one of $G, \bar{G}$ is connected.

Proof. If $V$ has only 1 element, the statement is trivially true. So suppose that $|V| > 1$. Let $\kappa = |V|$ and let $\varphi:\kappa\to V$ be a bijection. Suppose that neither $G$ nor $\bar{G}$ is connected. It is easy to see that this implies that there is a smallest $\alpha_0\in\kappa$ such that the induced subgraph $G_{\alpha_0}$ on the set $\text{im}(\varphi|_{\{0,\ldots,\alpha_0\}}) = \text{im}(\varphi|_{\alpha_0\cup \{\alpha_0\}}) \subseteq V$ has the property that neither $G_{\alpha_0}$ nor its complement $\bar{G}_{\alpha_0}$ is connected.

Case 1. $\varphi(\alpha_0)$ has no neighbors in the graph $G_{\alpha_0}$. But then $\varphi(\alpha_0)$ is connected to every vertex in $\bar{G}_{\alpha_0}$, so $\bar{G}_{\alpha_0}$ is connected, contradicting our assumption.

Case 2. $\varphi(\alpha_0)$ has no neighbors in the graph $\bar{G}_{\alpha_0}$. Same contradiction as Case 1.

Case 3. $\varphi(\alpha_0)$ has neighbors in the graph $G_{\alpha_0}$ as well as in the graph $\bar{G}_{\alpha_0}$. We know that at least one of $G_{\alpha_0}\setminus\{\varphi(\alpha_0)\}$ and $\bar{G}_{\alpha_0}\setminus\{\varphi(\alpha_0)\}$ is connected. We may assume that $G_{\alpha_0}\setminus\{\varphi(\alpha_0)\}$ is connected. But since there is an edge from some point in $G_{\alpha_0}\setminus\{\varphi(\alpha_0)\}$ to $\varphi(\alpha_0)$ by assumption of Case 3, we know that $G_{\alpha_0}$ is connected, contradicting our choice of $\alpha_0$.

Remark. The above proof used the well-ordering principle, which is equivalent to the Axiom of Choice (AC). It would be interesting to know whether the statement of the proposition above implies (AC).

Update. Will Brian gave a neat proof of the proposition above without using the Axiom of Choice, so the proposition does not imply (AC).