2
$\begingroup$

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)$?

$\endgroup$

3 Answers 3

9
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
2
  • $\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$
    – Tony Huynh
    Aug 30, 2017 at 12:37
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Can you provide more details? This answer is pretty thin as currently written $\endgroup$ May 27, 2016 at 23:49
  • $\begingroup$ @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. $\endgroup$
    – lixing
    May 28, 2016 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.