[Math] Let $G$ be a graph with $n$ vertices and $e$ edges. Let $m$ be the smallest positive integer such that $m \ge 2e/n$.

Question

Let $G$ be a graph with $n$ vertices and $e$ edges. Let $m$ be the smallest positive integer such that $m \ge 2e/n$.
Prove that $G$ has a vertex of degree at least $m$.

My approach is sum of all the degree of a graph is $2e$.
$d(v_1)+d(v_2)+……+d(v_n)=2e$.
then if we take the average, will get
$d(v)=2e/n$.
now this will be in between minimum degree and maximum degree in the graph.
Now $m$ also lies in between maximum and minimum degree of the graph.
From here how can we conclude the answer.
Please help me.

Answer 1

Now it's just a property of averages:

If $S$ is a finite set of integers, then $\max(S) \geq \lceil \mathrm{ave}(S) \rceil$.

Proof: If $S=\{s_i\}_{i=1}^n$, then \begin{align*} \max(S) & = \frac{\overbrace{\max(S)+\max(S)+\cdots+\max(S)}^{n \text{ times}}}{n} \\ & \geq \frac{s_1+s_2+\cdots+s_n}{n} & \text{since each } s_i \leq \max(S) \\ & = \mathrm{ave}(S) & \text{by definition}. \end{align*} And since $\max(S)$ is an integer, then $\max(S) \geq \lceil \mathrm{ave}(S) \rceil$.

In this case, we have $S$ as the set of degrees, and we can choose $m$ equal to the maximum degree, i.e., $m=\max(S)$.