If deleting 2 vertices decreases chromatic number by 2, then the graph is complete

Question

Let G be a finite graph such that, for any v, w ε V(G) with v ≠ w, one has χ((G − v) − w) = χ(G) − 2. Show that G is complete.

Answer 1

Assume that $G$ is not complete.

Then it has 2 non-adjacent vertices $v$ and $w$.

Let $\chi(G)=k$.

$G-v-w$ can be properly colored with $k-2$ colors. But now you can give $v$ and $w$ the same (new) color, since they are not adjacent, which gives you a proper $k-1$ coloring of $G$. Contradiction.