Prove that if $\chi(G-u-v)=\chi(G)-2$ for every vertices $u, v$ ($u \ne v$) then G is complete graph.

Question

I'm trying to prove this by contradiction: if $G$ isn't complete graph, there must exist vertices $u,v \in V(G)$ for which edge $uv \notin E(G)$. Then $u$ and $v$ must have the same color in proper coloring $C$ and now I'd like to prove that by removing $u, v$ we have $\chi(G-u-v) = \chi(G) - 1$ (that would be the contradiction), but I'm not sure whether it's true.

Answer 1

Consider the contrapositive of the statement instead:

If $G$ is not complete then $\exists u, v \neq u \text{ s.t. } \chi(G - u - v) \neq \chi(G) - 2 \quad \quad (1)$.

To prove (1), note that since $G$ is not complete, $\exists u, v \neq u$ with the same color in a proper minimal coloring of the graph; for such a pair of vertices we have that $\chi(G - u - v) \geq \chi(G) - 1$ and therefore $\chi(G - u - v) \neq \chi(G)-2$.

Answer 2

The accepted answer assumes a great deal about the existence of 2 vertices of the same color in the proper coloring of an incomplete graph $G$. It is better to assume less. Consider this proof by contradiction instead:

Assume $G$ is not a complete graph with $\chi(G)=n$ and that the statement holds. Then, $\exists$ vertices $u$, $v\neq w$ in $G$ s.t. $u$ is not adjacent to $v$. Remove these vertices and attain a graph $G-u-v$. By assumption, $\chi(G-u-v) = \chi(G) - 2 = n - 2$. Now, add back 2 vertices $u$, $v$ that are not adjacent to one another. This graph $G$ can clearly be colored in at most $(n-2) + 1 = n - 1$ colors since the maximum degree of any vertex is $\delta(G) = n - 1$, but this is a contradiction since $\chi(G) \leq n - 1 \implies n \leq n - 1$, a clear falsehood. Thus, $G$ is a complete graph if $\chi(G-u-v) = \chi(G) - 2$. $\Box$