Using the Well-Ordering Principle, which is equivalent to the [Axiom of Choice](https://en.wikipedia.org/wiki/Axiom_of_choice), it can be [proved](https://dominiczypen.wordpress.com/2018/04/09/any-graph-or-its-complement-is-connected/) that 



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


Does (S) imply (AC)?



Does the axiom of choice follow from the statement "Every simple undirected graph is either connected, or its complement is connected"?
(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$.


