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)$?
3 Answers
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.

$\begingroup$ 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}$ ? $\endgroup$ Jul 25, 2016 at 7:36

$\begingroup$ @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}})$. $\endgroup$ Aug 30, 2017 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 4uncolorable), δ(G) =5, is a counterexample.

$\begingroup$ Can you provide more details? This answer is pretty thin as currently written $\endgroup$ May 27, 2016 at 23:49

$\begingroup$ @DavidWhite Let G = (V,E ),E = 3V6. 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. $\endgroup$– lixingMay 28, 2016 at 1:01