Given a simple graph and its complement, prove that either of them is always connected.

Solution 1:

Suppose $G$ is disconnected. We want to show that $\bar{G}$ is connected. So suppose $v$ and $w$ are vertices. If $vw$ is not an edge in $G$, then it is an edge in $\bar{G}$, and so we have a path from $v$ to $w$ in $\bar{G}$. On the other hand, if $vw$ is an edge in $G$, then this means $v$ and $w$ are in the same component of $G$. Since $G$ is disconnected, we can find a vertex $u$ in a different component, so that neither $uv$ nor $uw$ are edges of $G$. Then $vuw$ is a parth from $v$ to $w$ in $\bar{G}$.

This shows that any two vertices in $\bar{G}$ have a path (in fact a path of length one or two) between them in $\bar{G}$, so $\bar{G}$ is connected.

Solution 2:

If $\bar G$, the complement of $G$, is not connected, then there exists a partitioning of vertices into two disjoint sets $V_1$ and $V_2$ such that no edge of the complement is between them, i.e. for all $v_1 \in V_1$ and $v_2 \in V_2$ we have $\langle v_1,v_2\rangle \notin \bar E$. However, this means that for all $v_1$ and $v_2$ from $V_1$ and $V_2$ respectively, $\langle v_1,v_2 \rangle \in E$, hence $G$ is connected.

I hope this helps ;-)

Solution 3:

I'm not very clever, and thinking gives me a headache. Let's try to solve this thing with a minimum of cleverness and hard thinking. A little brute force is OK.

Let's try for a proof by contradiction, that will always work if anything does. So we assume a disconnected graph $G$ with disconnected complement $\overline G.$

Then there are two vertices $a,b$ which can't be connected by a path in $G,$ and there are two vertices $c,d$ which can't be connected by a path in $\overline G.$

Let $H$ be the subgraph of $G$ induced by $\{a,b,c,d\},$ a graph with $2,3,$ or $4$ vertices depending on how $\{a,b\}$ and $\{c,d\}$ overlap. (Maybe I could eliminate one of those cases if I thought about it. Nuts to that.) If two vertices can't be connected by a path in the big graph, then they can't be connected by a path in the subgraph, right? So $H$ and $\overline H$ are still disconnected.

Great, that means I only have to check disconnected graphs with $2,3,$ or $4$ vertices. I can do that with brute force!

Allowing myself a tiny bit of cleverness to save work: If my disconnected graph $H$ has a disconnected complement, and if I can add edges to $H$ without making it connected, then the complement (which is losing edges) will still be disconnected! So I only have to test maximal disconnected graphs!! With just a little bit of thought, I see that a maximal disconnected graph is the disjoint union of two complete graphs. Up to $4$ vertices, the only graphs I have to check are: $$K_1\cup K_1,\ K_1\cup K_2,\ K_1\cup K_3,\ K_2\cup K_2.$$ The complements of those graphs are $$K_{1,1},\ K_{1,2},\ K_{1,3},\ K_{2,2}.$$ The complements are all connected! That does it!!

Wait a minute, that's looking suspiciously similar to the proofs in the other answers.