This is a short note of something that I wasn’t sure whether it is true for infinite graphs. Let be any simple, undirected graph, finite or infinite, such that . By we denote the complement of .
Proposition. At least one of is connected.
Proof. If has only 1 element, the statement is trivially true. So suppose that . Let and let be a bijection. Suppose that neither nor is connected. It is easy to see that this implies that there is a smallest such that the induced subgraph on the set has the property that neither nor its complement is connected.
Case 1. has no neighbors in the graph . But then is connected to every vertex in , so is connected, contradicting our assumption.
Case 2. has no neighbors in the graph . Same contradiction as Case 1.
Case 3. has neighbors in the graph as well as in the graph . We know that at least one of and is connected. We may assume that is connected. But since there is an edge from some point in to by assumption of Case 3, we know that is connected, contradicting our choice of .
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).