# Showing the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard

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.

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