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.


2 Answers 2


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$.


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$

  • $\begingroup$ Having them be the same color is equivalent to non-adjacency. $\endgroup$
    – Larry B.
    Sep 10, 2018 at 23:21
  • $\begingroup$ I agree that stating they are the same color $\implies$ they are not adjacent, but stating they are not adjacent, the clear result of assuming the graph $G$ is not complete, does not imply they are the same color in a given coloring. It may be true that you can prove this, but it's a hefty and unnecessary lemma to the proof. My professor tore my usage of this proof apart today on this point. I didn't state that your proof was wrong, it just makes more assumptions than the one I provided. $\endgroup$ Sep 10, 2018 at 23:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .