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$
8
$\begingroup$

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

$\endgroup$
6
$\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$
  • $\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$ – Dominic van der Zypen Jul 25 '16 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 '17 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$
  • $\begingroup$ Can you provide more details? This answer is pretty thin as currently written $\endgroup$ – David White May 27 '16 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$ – goodboy May 28 '16 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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