Problem 1007

Let $G$ be a non-connected graph.

Then it has at least two connected components, and in particular there exists a coloring of $G$ with two colors (for example, blue and green) such that no vertex of one color is in the same connected component as a vertex of another color (and that both colors appear).

Given two vertices $v_{1}$ and $v_{2}$, we proceed by case analysis.

- If $v_{1}$ and $v_{2}$ are of different colors, they are not in a common connected component, in particular they are not adjacent in $G$ and therefore are adjacent in $\bar{G}$ and thus in particular in the same connected component in $\bar{G}$.
- If $v_{1}$ and $v_{2}$ are of the same color. Without loss of generality, assume they are both blue.

Let $w$ be a green vertex (which exists by hypothesis).

Then, as before, $v_{1}$ and $w$ are adjacent in $\bar{G}$ and $v_{2}$ and $w$ are adjacent in $\bar{G}$. Consequently, $\left(v_{1}, w, v_{2}\right)$ is a path from $v_{1}$ to $v_{2}$ in $\bar{G}$.

Thus, in all cases, there exists a path between $v_{1}$ and $v_{2}$.

We note that we have in fact shown much more: not only does a path exist, but we can arrange for this path to have length 1 or 2 (depending on whether $v_{1}$ and $v_{2}$ are or are not in the same connected component of $G$).