As the title states, I need to prove that the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard.

I'm not looking for a solution but a clue or something to help me develop the intuition for coNP questions would be very useful.

I've tried reducing the $\overline{\text{3-Col}}$ problem to it and failed, and I also tried reducing the similar $\overline{\text{3-Col}}\cup\text{2-Col}$ (because I proved it's complement to be an NP-complete problem) but didn't get anywhere because. In both cases I just wasn't able to ensure that given a not-3-colorable graph I'd output a 4-colorable one.

As always your time and help are appreciated.


1 Answer 1


Let's flip this around using the fact that $L$ is $\text{NP}$-hard iff $\overline{L}$ is $\text{coNP}$-hard. You want to show that $$\text{3-Col} \cup \overline{\text{4-Col}} \text{ is NP-hard}.$$ To do this, we should dig in a little to the proof that $\text{3-Col}$ is $\text{NP}$-hard. The usual proof of this is a reduction from $\text{3-SAT}$ that for every 3CNF formula $\phi$ constructs a graph $G$ such that $$\phi \in \text{SAT} \iff G \in \text{3-Col}.$$ I want you to take a closer look at that reduction. If we can prove that $G$ is always 4-colorable then we're done; be careful to properly do the casework that shows $$\phi \in \text{SAT} \iff G \in \text{3-Col} \cup \overline{\text{4-Col}} .$$

  • $\begingroup$ Thanks a lot, I'll look into it $\endgroup$ Commented May 26 at 7:04
  • 2
    $\begingroup$ I went for 3NAE in the end because it was a bit easier for me, but the general idea looks the same, so thanks a lot! $\endgroup$ Commented May 26 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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