# Critical with respect to chromatic, but not Hadwiger number

For any simple, undirected graph $G=(V,E)$ where $V$ is finite, we define the Hadwiger number $\eta(G)$ to be the maximum $n$ such that $K_n$ is a minor of $G$.

Is there a graph $G$ on such that removing a vertex or contracting an edge reduces the chromatic number, but has no effect on the Hadwiger number?

To be more precise, I'm looking for a graph $G$ such that

1. $G$ is vertex-critical (for any $v\in V(G)$ we have $\chi(G\setminus\{v\}) = \chi(G) - 1$);
2. $G$ is edge-contraction-critical (for any $e\in E(G)$ contracting $e$ reduces the chromatic number);
3. for any $v\in V(G)$ we have $\eta(G) = \eta(G\setminus \{v\})$;
4. for any $e\in E(G)$ contracting $e$ does not change the Hadwiger number.

Here's an example that does not require a computer or exercises left to the reader. Let $$G$$ be the graph obtained by taking two $$7$$-cycles $$C_1$$ and $$C_2$$ and joining each vertex of $$C_1$$ to each vertex of $$C_2$$. The chromatic number of this graph is $$6$$ since $$\chi(C_1)=\chi(C_2)=3$$. The Hadwiger number of this graph is $$7$$ (we get a $$K_7$$ by contracting a perfect matching between $$V(C_1)$$ and $$V(C_2))$$. Deleting a vertex yields a path on one side, so the chromatic number goes down to $$5$$. Contracting an edge of $$C_1$$ or $$C_2$$ gives a $$6$$-cycle on one side, so the chromatic number goes down to $$5$$. Contracting an edge between $$V(C_1)$$ and $$V(C_2)$$ yields two $$7$$-cycles $$C_1'$$ and $$C_2'$$ meeting at a vertex $$v$$, together with all edges between $$V(C_1') \setminus v$$ and $$V(C_2') \setminus v$$. This graph is obviously $$5$$-colourable, since there is a $$3$$-colouring of $$C_1'$$ where only $$v$$ is coloured red. Finally, deleting a vertex or contracting an edge does not change the Hadwiger number, since in either case the resulting graph still contains $$K_{6,7}$$. Contracting a matching of size $$6$$ in $$K_{6,7}$$ yields a $$K_7$$-minor.

Edit. Having read my answer again after a few years, I see a mistake in the above argument. The Hadwiger number of $$G$$ is actually $$8$$ (not $$7$$ as claimed), since contracting the edges of a matching of size $$6$$ between $$V(C_1)$$ and $$V(C_2)$$ yields a $$K_8$$-minor. Thus, the Hadwiger number of $$G$$ appears to go down when contracting an edge of $$C_1$$ or $$C_2$$.

Here's one for you: Although it is not drawn planar, it is planar, and so it has no $K_5$-minor. However it has lots of $K_4$-minors. For example, the $0,4,6,8$ induces $K_4\backslash e$ and so adding any path from $4$ to $6$, say $4-7-1-6$ gives a graph that can be contracted to $K_4$. So this shows that deleting $2$ or $3$ or $5$ still leaves a $K_4$-minor. The remaining cases are similar and left as an exercise!

As for the colouring, it is easy to see that it is not $3$-colourable just by working with the triangles (start with $0$ red, $6$ green and $8$ blue and follow your nose). But contracting any edge leaves a $3$-chromatic graph.

You can see this easily enough by hand, or just run this code:

g = Graph("H?vAqz")
for e in g.edges():
h = copy(g)
h.merge_vertices([e,e])
print h.chromatic_number()
`