Let $G$ be a graph such that $\chi(G - x - y) = \chi(G) - 2$, for all distinct vertices $x,y$. Prove that $G$ is complete.

Question

I understand that it's a complete graph because $\chi(K_n) = n$ (by Brooks theorem), so when we start cutting vertices, with $K_{n-1}$ we will have $\chi(K_{n-1}) = n-1$. My question is how would I prove this, I keep getting to a road block on just how to say it in a mathematical sense.

Answer 1

Suppose $G$ is not a complete graph. So there exist two vertices, say $x$ and $y$ such that x is not connected to $y$. Let $f : V (G − x − y) → [χ(G) − 2]$ be a proper $(χ(G) − 2)$-coloring of $G$. Create a new color and assign it to both $x$ and $y$ to create a proper $(χ(G)−1)-$ coloring of $G$, a contradiction.