Skip to main content
1 of 4

Complete minors and minimal degree

Is there for every positive integer $n\in\mathbb{N}$ a finite, simple, undirected graph $G=(V,E)$ with the following properties?

  1. for all $v\in V$ we have $\text{deg}(v) \geq k$, and
  2. $G$ does not have a complete minor with more than $\frac{k}{n}$ points.