Is it true that any finite graph has a $K_n$ minor, where $n$ is a minimal vertex degree?
$\begingroup$
$\endgroup$
1
asked Jan 31, 2020 at 14:18
-
$\begingroup$ Not if the graph is infinite (e.g. $n=3$ and the infinite binary tree). $\endgroup$– M. WinterCommented Jan 31, 2020 at 14:37
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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).
answered Jan 31, 2020 at 14:39
-
2$\begingroup$ This is a great (counter)example. $\endgroup$ Commented Jan 31, 2020 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$ Commented Feb 1, 2020 at 7:11
$\begingroup$
$\endgroup$
2
More generally, it is a classic result (independently due to Kostochka and Thomason) that minimum degree $(\alpha+o(1))n \sqrt{\log n}$ suffices to force a $K_n$ minor, where $\alpha$ is an explicit constant. Conversely, there are random graphs with minimum degree $\Omega(n\sqrt{\log n})$ that do not contain a $K_n$ minor. See here to access the paper by Thomason.
Update. Alon, Krivelevich, and Sudakov have recently given a new short proof of the Kostochka-Thomason result.
answered Jan 31, 2020 at 16:36
-
1$\begingroup$ Where can I read about this in detail? $\endgroup$ Commented Feb 1, 2020 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$ Commented Feb 1, 2020 at 5:22