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

Advertisements

About dominiczypen

I'm interested in general topology, order theory, and graph theory. This link takes you to my preprints on arXiv.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s