Let $G = (V,E)$ be a graph with $|V|=n$ and $|E|=e$.

Question

Let $G = (V,E)$ be a graph with $|V|=n$ and $|E|=e$. Let $M = \max_{v\in V} \deg(v)$ and $m = \min_{v\in V} \deg(v)$. Show that $m\leq 2e/n \leq M$.

How do I approach this problem? I am especially confused by $m\leq 2e/n \leq M$.

Answer 1

You may be familiar with this theorem:

In a graph $G$, the sum of the degrees of the vertices is equal to twice the number of edges.

With your notation this would mean that $$\sum_{v \in V} \deg(v)=2e.\tag{1}$$ Now, for every $v \in V$ we have that $\deg(v)$ can be any number such that $$ m \leq \deg(v) \leq M. \tag{2}$$ So, suppose $V=\{ v_1,v_2,\ldots,v_n\} $ is your vertex set. As a consequence of $(2)$ we have that $$\underbrace{m+m+\ldots+m}_{n \text{ times}} \leq \deg{(v_1)+\deg{(v_2)}+\ldots+\deg{(v_n)}}\leq \underbrace{M + M + \ldots+M}_{n \text{ times}}$$ Notice the LHS reduces to $m \cdot n$, RHS reduces to $M\cdot n$ and because of the first theorem we have that $\deg{(v_1)+\deg{(v_2)}+\ldots+\deg{(v_n)}} = 2e$. Thus

$$m\cdot n \leq 2e \leq M \cdot n \implies m\leq \frac{2e}{n} \leq M.$$

Answer 2

Note that $2e/n$ is the average degree. The result is immediate from this observation.