# Does Hadwiger conjecture imply that NP = coNP?

(Disclaimer: I suspect the answer is no, but I fail to see why)

Here is a nice picture by David Epstein (taken from Wikipedia) illustrating Hadwiger's conjecture:

The point is that if in a given graph $$G$$ some-one gives you four connected subgraphs $$G_1$$, $$G_2$$, $$G_3$$, $$G_4$$ (here illustrated with grey boxes) such that for each of the six combinations $$(i, j)$$ there is at least one edge in $$G$$ connecting a vertex in $$G_i$$ to one in $$G_j$$, then the conjecture claims that there is no 3-coloring of the big graph $$G$$.

Suppose that Hadwiger's conjecture is true. Wouldn't this put 3-coloring in coNP? At least to me it seems that once someone gives you $$G_1, G_2, G_3, G_4$$ their connectedness and existence of 6 edges connecting the four subgraphs can be checked in time quadratic in the number of vertices of the big graph $$G$$.

But if indeed 3-coloring is in coNP, wouldn't that put all of NP in coNP thus making these complexity classes equal?

This seems wrong, my impression was that both Hadwiger's conjecture and $$NP \neq coNP$$ are widely believed, so most likely something is wrong with my reasoning above.

But what?

I think the problem here is that you are stating the converse of Hadwiger's conjecture. The conjecture (according to Wikipedia) states that "if a graph needs at least k colors for a proper coloring, then it contains a $$K_k$$ minor (i.e. there exist subgraphs $$G_1,\ldots,G_k$$ as you state)". You are talking about the assertion that "If a graph has a $$K_k$$ minor, then it needs at least k colors for a proper coloring".
These two are not equivalent. Indeed, the latter statement is false. Consider for example a $$K_{n,n}$$. This graph contains a $$K_n$$ minor (take a perfect matching, this gives a collection of $$n$$ connected components all of which have edges to each other). However, its chromatic number is 2.