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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.