Show that for any simple graph G one of G and G′ is connected.

Question

I'm having some trouble making sense of this question in my Homework.

If G is a simple graph, then the complement, G′, is obtained as follows. If the vertices a and b are joined by an edge in G then there is no such edge in G′, while if there is no edge between a and b in G, then there is an edge joining these vertices in G′. Show that for any simple graph G one of G and G′ is connected.

If you can shed any light that would be extremely helpful.

Answer 1

Let $G$ be a simple graph. We want to show either $G$ or $G'$ is connected.

If $G$ itself is connected, you're done, so we assume that $G$ is not connected (this is a common way of approaching `$A$ or $B$' type proofs, you assume not $A$ and then try prove $B$ from that assumption).

If $G$ is not connected, then it has at least two connected components. So we can divide $G$ into two pieces, $H$ and $K$, such that there are no edges from $H$ to $K$.

Now from this setup, see if you can show that for any two vertices $u$ and $v$ of $G$, you can find a $u-v$ path in the complement $G'$. Click the spoiler below for a hint.

There are two cases to consider. Either both $u$ and $v$ are in the same part (so both lie in $H$ or both lie in $K$, or they lie in different parts (so maybe $u$ is in $H$ and $v$ in $K$).

For a full proof, click the next spoiler:

Case 1: Both $u$ and $v$ lie in $H$. Let $w$ be a vertex of $K$. Since $u$ and $v$ are not adjacent to $w$ in $G$, they must both be adjacent to $w$ in $G'$, so $u-w-v$ is a $u-v$ path in $G'$. Case 2: $u$ is in $H$ and $v$ is in $K$. In this case, $u$ and $v$ are not adjacent in $G$, so they must be adjacent in $G'$. In any case, we have a $u-v$ path in $G'$, so $G'$ is connected.