0
$\begingroup$

For a finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ and $\Delta(G)$ denote the minimum and maximum degree of $G$, respectively.

Is there a constant $K\in\mathbb{N}$ with the following property?

Whenever $n,k$ are integers with $n\geq 4, k\geq 1$ and $n>k$, there is a $k$-vertex critical graph $G=(V,E)$ with $|V|=n$ and $\Delta(G)-\delta(G) \leq K$.

$\endgroup$
2
  • 1
    $\begingroup$ k-[vertex critical] ? $\endgroup$
    – Wlod AA
    Dec 15, 2019 at 0:53
  • 1
    $\begingroup$ Right - forgot to insert link, will do. $\endgroup$ Dec 15, 2019 at 7:52

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.