Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Suppose you have a k critical graph on k+1 vertices. If there exists a vertex of degree less than k-1, remove it. By assumption you can k-1 color the remaining graph. However if you add back in the vertex removed it can only be adjacent to k-2 colors, so we can complete it to give a k-1 coloring of the whole graph. So we can assume every vertex has degree k-1 or k.

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.

share|improve this answer
    
Thanks.. great proof.I have just one doubt.How can we prove that a pair of non adjacent vertex exist with k-1 one degree. Can't we have a graph with just one vertex with k-1 or degree or just one pair of adjacent vertex having k-1 degree –  Neel Choudhury Nov 29 '13 at 5:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.