0

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.

RobPratt
  • 45,619
Jane Kent
  • 1
  • 1
    Is there any particular part where you get stuck? – Rushy Oct 19 '20 at 10:47
  • 1
    This is a good question, and it is well-posed. Except for one thing: many frequent users of this site like questions where the asker showed some effort, typically in the form of including their own attempt at the solution. If you would do this, it would also help us to pinpoint what you are struggling with, which results in better answers (hence Rushy's question). It would also encourage more users (including me) to answer this question. – Aldoggen Oct 19 '20 at 12:45
  • You can prove it using induction on the number of vertices. – Jaap Scherphuis Oct 19 '20 at 14:23

1 Answers1

3

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

enter image description here

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.

Brandon du Preez
  • 4,253