7
$\begingroup$

Is it true that any finite graph has a $K_n$ minor, where $n$ is a minimal vertex degree?

$\endgroup$
  • $\begingroup$ Not if the graph is infinite (e.g. $n=3$ and the infinite binary tree). $\endgroup$ – M. Winter Jan 31 at 14:37
15
$\begingroup$

No.

The edge-graph of the icosahedron is regular of degree five, but does not have a $K_5$ minor because it is planar (Kuratowski's theorem).

$\endgroup$
  • $\begingroup$ This is a great (counter)example. $\endgroup$ – Steven Stadnicki Jan 31 at 17:00
  • $\begingroup$ Also the smallest if I am not mistaken. No $K_4$-minor means the graph has a vertex of degree 2. $\endgroup$ – Gordon Royle Feb 1 at 7:11
16
$\begingroup$

More generally, it is a classic result (independently due to Kostochka and Thomason) that minimum degree $O(n \sqrt{\log n})$ suffices to force a $K_n$ minor, and conversely, there are graphs with minimum degree $\Omega(n\sqrt{\log n})$ that do not contain a $K_n$ minor. Moreover, we know precisely what the constant term should be. See here to access the paper by Thomason.

$\endgroup$
  • 1
    $\begingroup$ Where can I read about this in detail? $\endgroup$ – Eschatum Verus Feb 1 at 3:00
  • 3
    $\begingroup$ I added a link to the corresponding paper by Thomason. Note that Thomason's result is stated for average degree, but every graph with average degree $d$ contains a subgraph of minimum degree $\frac{d}{2}$. $\endgroup$ – Tony Huynh Feb 1 at 5:22

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.