# Hadwiger number and minimal degree

Suppose $G$ is a finite simple graph and $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$. If $\delta(G)$ is the minimal degree of $G$, do we have $\delta(G)\leq\eta(G)$?

No, icosahedron does not have $K_5$ as a minor being planar graph.

This is false by classic results of Kostochka and Thomason. Indeed, the claim is false even if you replace 'minimum degree $t$' with '$t$-connected'. That is, if you define $\nu(t)$ to be the smallest Hadwiger number among all $t$-connected graphs, then Corollary 5 of this paper of Kostochka shows that $\nu(t)$ is $O(\frac{t}{\sqrt{\ln t}})$.

On the other hand, just having average degree at least $(\alpha+o(1))t \sqrt{\ln t}$, where $\alpha=0.638\dots$ is an explicit constant is enough to force a $K_t$-minor.

• Thanks Tony -- just a little question, do your remarks imply that for any positive integer $n$ there is a finite connected graph $G$ such that $\frac{\eta(G)}{\delta(G)}<\frac{1}{n}$ ? – Dominic van der Zypen Jul 25 '16 at 7:36
• @DominicvanderZypen Yes, by the first paragraph,for every $t$ there is even a $t$-connected graph $G$ with $\frac{\eta(G)}{\delta(G)}=O(\frac{1}{\sqrt{ \ln t}})$. – Tony Huynh Aug 30 '17 at 12:37

There are infinite many planar graph , δ(G) =5 but η(G) < 5 definitely.

Let G is a counterexample, H = n*G, H is also a counterexample.

A faked smallest planar graph G (suppose 4-uncolorable), δ(G) =5, is a counterexample.

• Can you provide more details? This answer is pretty thin as currently written – David White May 27 '16 at 23:49
• @David-White Let G = (V,E ),E = 3V-6. If d(Vi) = 5 for all Vi, then V = 12 through solving the equation : 2E = 5V , it is icosahedron, a counterexample . Similarly there are infinite different equations with different conditions ( d(Vi) >= 5) , solve them. Or in a more simple way to understand the conclusion: let G = n*counterexample , G is a counterexample. – goodboy May 28 '16 at 1:01