Skip to main content
3 of 4
While clear from context and tradition, it was not mentioned anywhere so far that $n=\lvert V\rvert$. Added this.

Complete minors and minimal degree

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

$G$ does not have a complete minor with more than $\frac{\delta(G)}{n}$ points (where $\delta(G)$ denotes the minimal degree).