Upper Bounding A Sum of Powers of Degrees in a Graph

33 Views Asked by At

Let $G$ be a simple, directed graph with $n$ vertices and $m$ edges. Let $V$ denote the vertex set of $G$. Given a vertex $v$ in $G$, let $\deg_{\text{out}}(v)$ denote its outdegree. Finally, let $\omega \in (2,3)$ be some constant.

It's mentioned on page 196, Section 4.1 of this paper that for some constant $C > 0$, the following inequality holds:

$$\sum_{v\in V} \deg_{\text{out}}(v)^{\omega - 1} \le Cmn^{\omega - 2}.$$

My question is: why does the above inequality hold?

It seems like it should be easy to prove this result somehow using the facts that $\deg_{\text{out}}(v)\le n$ for all vertices $v$, and that $\sum_{v\in V}\deg_{\text{out}}(v) = m$, but I do not immediately see how to prove that the above inequality holds.