Does Hadwiger conjecture imply that NP = coNP?

Question

(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?

Answer 1

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.