# k critical graph cannot have k + 1 vertices

$k$-chromatic graph is called $k$-critical if removal of any vertex from graph makes it $k - 1$ vertex colorable.

Now i have to prove that if $G$ is a $k$ critical graph then it cannot have $k+1$ vertices.

I can see that the property is true as a triangle is 3 critical. Also we have a 5-cycle as 3 critical but no $4$ vertex graph is $3$ critical.

Can any one help me in what direction i should prove the theorem

-

Now choose a pair of degree k-1 not adjacent to one another, they must both be adjacent to all other vertices. (Not all vertices can have degree k, as $K_{k+1}$ is not k chromatic) Remove one, k-1 color the resulting graph then add back in the vertex giving it the same color as the other vertex in the pair. This is a valid k-1 coloring.