Reduction from 4COL to 3COL I have a problem with following task: $4COL \in PTIME \Rightarrow 3COL \in PTIME$.

Is there any elementary proof to do it?
Your question is answered in a blog post of Lance Fortnow. Solutions are given by Fortnow and by Lovász.