Existence of a graph with $\lfloor \frac{2m}{\delta} \rfloor$ vertices for arbitrary $m$ and $\delta$ 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.
 A: 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.
