Is there for every positive integer $n\in\mathbb{N}$ a finite, simple, undirected graph $G=(V,E)$ with 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).


Not an answer but an observation: for any fixed order $r$ of the complete minor, your question can be answered by a finite search over the set of all graphs of order at most $c_{\mathrm{Kostochka}}\sqrt{\log r}$: let any $n\in\mathbb{N}$ be given. Let any graph $G=(V,E)$ be given. Let $\delta:=\delta(G)$. Let $c=c_{\mathrm{Kostochka}}>0$ denote the absolute constant in Theorem 7.2.3 of Diestel, Graph Theory, fourth ed. Since $\mathbb{R}_{>1}\to\mathbb{R}$, $r\mapsto cr(\log r)^{1/2}$ is strictly monotone increasing, there exists a unique solution $r=r(\delta)$ to the equation $\delta=cr(\log r)^{1/2}$. Theorem 7.2.3 says that $K^{r(\delta)}\preceq G$. So we may assume that

$r(\delta)\leq \delta/n$


$n\leq c(\log r)^{1/2}$.


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.