# Does minimal degree $n$ imply a $K_n$ minor

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

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

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).
• Also the smallest if I am not mistaken. No $K_4$-minor means the graph has a vertex of degree 2. – Gordon Royle Feb 1 at 7:11
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.
• 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}$. – Tony Huynh Feb 1 at 5:22