Existence of a graph with $\lfloor \frac{2m}{\delta} \rfloor$ vertices for arbitrary $m$ and $\delta$

graph theory

We know that if a simple graph $G$ has $m$ edges and the minimum degree of its vertices is $\delta$ and $\delta \leq \lfloor \frac{2m}{\delta} \rfloor – 1 $ then it has at most $\lfloor \frac{2m}{\delta} \rfloor$ vertices. I know how to deduce the inequality but I don't know how to show that there exists some simple graph of size $m$ and of minimum degrees $\delta$ such that it has exactly $\lfloor \frac{2m}{\delta} \rfloor$ vertices since this is necessary to show for being the maximum number of vertices.

Best Answer

Erdős-Gallai theorem will get the job done, but is an overkill here. You can simply construct such a graph:

First some necessary conditions:

  • $\delta>0$ obviously
  • $m\leq\binom{\lfloor 2m/\delta\rfloor}2$ to ensure there is a simple graph on $\lfloor\frac{2m}\delta\rfloor$ vertices (counterexample: if $m=\binom{\delta+1}2+1$, then $\lfloor 2m/\delta\rfloor=\delta+1$ but that is more edges than the complete graph).
  • $\delta\leq\lfloor\frac{2m}\delta\rfloor-1$ to guarantee vertex degree $\delta$ is possible in a simple graph on $\lfloor\frac{2m}\delta\rfloor$ vertices.
  • $m-\delta$ edges on $\lfloor\frac{2m}\delta\rfloor-1$ vertices are possible: $$ m-\delta\leq{\lfloor\frac{2m}\delta\rfloor-1\choose 2} $$ for removing a vertex of degree $\delta$.

Lemma: For any $m,n\in\mathbb{N}$ with $m\leq\binom{n}2$, there exists a simple graph $G$ of order $n$ and size $m$ such that $\Delta(G)-\delta(G)\leq 1$. Let's call these graphs almost regular.

Proof: The given conditions guarantee the existence of a simple graph of order $n$ and size $m$. We iteratively bring the degrees closer:

  • if $\Delta(G)-\delta(G)\leq 1$, stop
  • otherwise pick a vertex $v$ with degree $\Delta(G)$ and a vertex $v'$ of degree $\delta(G)$. Since $\Delta(G)>\delta(G)+1$, there is some $w\in\Gamma(v)-\Gamma(v')$. Replace edge $vw$ by $v'w$. This decreases $\deg v$ by 1 and increases $\deg v'$ by 1.
  • Repeat.

This process must terminate since we are decreasing $\sum_v\deg(v)^2$. The resulting graph $G$ has $k$ vertices of degree $\delta(G)$ and $n-k$ vertices of degree $\delta(G)+1$, some $k\in[1,n]$. $\square$

In particular, we have $$ k\delta(G)+(n-k)(\delta(G)+1)=2m $$ so $$ \delta(G)=\left\lceil\frac{2m+1}{n}\right\rceil-1. $$

So if $$ \left\lceil\frac{2m+1}{\lfloor 2m/\delta\rfloor}\right\rceil-1=\delta $$ we are done. Otherwise, we have $$ \left\lceil\frac{2m+1}{\lfloor 2m/\delta\rfloor}\right\rceil-1>\delta. $$ By the Lemma, we can pick an almost regular graph $G$ of order $\lfloor 2m/\delta\rfloor-1$ and size $m-\delta$. This graph has minimum degree $$ \left\lceil\frac{2m-2\delta+1}{\lfloor 2m/\delta\rfloor-1}\right\rceil-1\geq\delta $$ so just add a new vertex $v$ and pick $\delta$ neighbours.

Related Question