Let $G$ be a graph with $n$ vertices and $e$ edges. Let $m$ be the smallest positive integer such that $m \ge 2e/n$. 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.
 A: 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)$.
A: Suppose that there does not exist a vertex $v$ such that $\deg(v) \geq m$. Then the sum of the degrees of all vertices in $G$, $\sum_{i=1}^{n}v_i \leq (m-1)n$. Since $\sum_{i=1}^{n}v_i=2e$, we have $2e\leq(m-1)n$. Divide both sides by $n$ to get $\frac{2e}{n} \leq m-1$. So, we have $\frac{2e}{n}+1 \leq m$. This is a contradiction because if $\frac{2e}{n}$ is an integer, then $m=\frac{2e}{n}$ and if $\frac{2e}{n}$ is not an integer, $m=\frac{2e}{n}+c$ for some rational number $0<c<1$.
