Proof: $G^*$ is connected

Given: $G = (V, E)$ is a simple graph on $n$ vertices ($n \geq 2$) with no self-loops and exactly two connected components.

To prove: The complement graph $G^*$ of $G$ is connected.

---

Definitions and Preliminary Observations

1. The complement graph $G^*$ of $G$ is a graph on the same vertex set $V$, where $\{u, v\} \in E^*$ if and only if $\{u, v\} \notin E$ (i.e., an edge exists in $G^*$ if it does not exist in $G$).

2. $G$ has exactly two connected components:

   • Let the connected components of $G$ be $C_1$ and $C_2$.
   • Every vertex belongs to exactly one of $C_1$ or $C_2$, and there are no edges between vertices in $C_1$ and $C_2$.

3. Key observation: In $G^*$, there must be at least one edge between any vertex in $C_1$ and any vertex in $C_2$, since $G$ has no edges between these two components.

---

Proof Strategy

We prove that $G^*$ is connected by showing that for any two vertices $u, v \in V$, there exists a path between $u$ and $v$ in $G^*$. Consider the following two cases:

---

Case 1: $u$ and $v$ are in different connected components of $G$

• Without loss of generality, assume $u \in C_1$ and $v \in C_2$.

• Since $G$ has no edges between $C_1$ and $C_2$, the complement $G^*$ has edges between every pair of vertices in $C_1 \times C_2$. Thus, there is a direct edge $\{u, v\} \in E^*$.

• Therefore, $u$ and $v$ are connected in $G^*$.

---

Case 2: $u$ and $v$ are in the same connected component of $G$

• Without loss of generality, assume $u, v \in C_1$.

• In $G^*$, there are edges between every vertex in $C_1$ and every vertex in $C_2$ (from Case 1). Let $w$ be any vertex in $C_2$.

• A path from $u$ to $v$ in $G^*$ can be constructed as: $u \to w \to v$ Here:

  • $u \to w$ exists because $\{u, w\} \in E^*$.
  • $w \to v$ exists because $\{w, v\} \in E^*$.

• Thus, $u$ and $v$ are connected in $G^*$.

---

Conclusion

By considering both cases, we see that any two vertices $u, v \in V$ are connected by a path in $G^*$. Therefore, $G^*$ is connected.

---

Key Intuition and Final Notes

• The disconnected nature of $G$ (having two connected components) forces $G^*$ to be connected, because the complement fills in the "gaps" between the components.
• The critical edges in $G^*$ are those between vertices in $C_1$ and $C_2$, ensuring connectivity across the graph.

---

Do you have further questions or need clarification on any steps?

---

Related Questions

1. What happens if $G$ has three or more connected components?
2. How can you generalize this result to $G$ with arbitrary connected components?
3. Can a graph and its complement both be disconnected? Why or why not?
4. How does the number of vertices $n$ affect the structure of $G^*$?
5. Is there a similar property for complements of graphs with other constraints (e.g., bipartite graphs)?

Tip: When working with complement graphs, think about the edges in $G$ and $G^*$ as "filling in" each other's missing connections.