<p>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 <span class="math-container">$K_k$</span> minor (i.e. there exist subgraphs <span class="math-container">$G_1,\ldots,G_k$</span> as you state)". You are talking about the assertion that "If a graph has a <span class="math-container">$K_k$</span> minor, then it needs at least k colors for a proper coloring".</p>

<p>These two are not equivalent. Indeed, the latter statement is false. Consider for example a <span class="math-container">$K_{n,n}$</span>. This graph contains a <span class="math-container">$K_n$</span> minor (take a perfect matching, this gives a collection of <span class="math-container">$n$</span> connected components all of which have edges to each other). However, its chromatic number is 2.</p>

CC BY-SA 4.0
2019-04-03T11:23:11.587Z
Yes that's it, thank you!
Vincent
CC BY-SA 4.0
2019-04-03T10:52:12.923Z
2019-04-03T10:52:12.923Z
Michael Lampis
<p>(Disclaimer: I suspect the answer is no, but I fail to see why)</p>

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

<p><a href="https://i.sstatic.net/nkVS4.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/nkVS4.png" alt="ph"></a></p>

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

<p>Suppose that Hadwiger's conjecture is true. Wouldn't this put <code>3-coloring</code> in coNP? At least to me it seems that once someone gives you <span class="math-container">$G_1, G_2, G_3, G_4$</span> 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 <span class="math-container">$G$</span>.</p>

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

<p>This seems wrong, my impression was that both Hadwiger's conjecture and <span class="math-container">$NP \neq coNP$</span> are widely believed, so most likely something is wrong with my reasoning above.</p>

<p>But what?</p>

<cc.complexity-theory><graph-theory>
Does Hadwiger conjecture imply that NP = coNP?
Vincent
# Does Hadwiger conjecture imply that NP = coNP?

(Asked by: username_0 on 2019-04-03)

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

[![ph](https://i.sstatic.net/nkVS4.png)](https://i.sstatic.net/nkVS4.png)

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?

**Tags:** cc.complexity-theory, graph-theory

---

## 1 answers

### Answer by username_1 on 2019-04-03. Score: 16 | Accepted answer

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.

> **Comments:**
> **username_0**: Yes that's it, thank you!  

---

