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)?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityUsing 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$.