Let G be a simple graph with n vertices and m edges. Prove the following holds using the Handshake Theorem:
$$\frac{m}{\Delta} \leq \frac{n}{2} \leq \frac{m}{\delta}$$
where: $\Delta$ is the maximum degree of V(G)
and $\delta$ is the minimum degree of V(G)
I am preparing for my final and this is a question I should be able to solve. Graph theory is perhaps 3 days old for me at this point and so I am really just stuck on this.
I would appreciate any help. What will help the most is a thorough explanation of why a proof for this is how it is. Proving things in graph theory feels…odd…so far.
Best Answer
Start with $\Delta \ge$ average degree $\ge \delta$ for any graph.
We know that the total degree is $2m$ by the Handshake Lemma, so the average degree is $=\frac{2m}{n}$. So $\Delta \ge\frac{2m}{n}\ge \delta$.
Now, let m divide all three sides, changing the $\ge$ to $\le$: $$\frac{m}{\Delta}\le\frac{n}{2}\le\frac{m}{\delta}$$