Is the maximum degree in a simple connected graph =$o(|E|)$?

Question

I am trying to prove something, and it will help e greatly to show that the maximum degree of any vertex, $d$ is a connected simple graph, goes up asymptotically linearly along with the number of edges in the graph.

I came up with a somewhat hand-wavey "proof", and I wonder if it is anywhere near correct:

For fixed $|V|=n$, as $m$ grows, so does $d$, linearly, with constant average $\frac{1}{n}$, as by the pigeonhole principle, for every addition of n edges, the maximum degree has to increase by at least 1.

---

The other direction is easily $m \le \frac{dn}{2}$.

---

I wonder if this is at all correct, and if so, how to improve the proof

Answer 1

The idea is correct. Indeed, if $d$ is the maximal degree in the graph, $n$ is the number of nodes and $m$ is the number of edges, we can give the following bounds on $d$: Define $d_v$ to be the degree of $v$, for any node $v\in V$.

1. $d\le \min\{m,n\}$
2. $\lfloor\frac{2m}{n}\rfloor \le d$

The first bound is given by the fact that $d$ has at most $\min \{m,n\}$ edges. This is the correct way to bound $d$ from above, and in fact is the tightest bound we can give.

The second bound is actually the bound you proved (which is the interesting bound), using the pigeonhole principle. The "correct" way to use the pigeonhole principle is to use its extended version. Say there are $m$ edges, then the sum of the degrees is $2m$. We distribute them into $n$ nodes, to get that at least one node has to have degree at least $\lfloor\frac{2m}{n}\rfloor$. The maximal degree has to be at least as big, hence $d\ge \lfloor \frac{2m}{n}\rfloor$.