# Let G be a simple graph with n vertices and m edges. Prove the following holds!!

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.

## 1 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}$$

• Oh this is simple. Thanks for the help, n55. We spent all of 20 seconds on this theorem in class. – 123 Jul 1 '15 at 1:25
• You're welcome. Good luck on your final! – n55 Jul 1 '15 at 1:27
• Thanks. I am sure there will be several more graph theory questions from my tonight...stay tuned if you enjoy solving such problems! – 123 Jul 1 '15 at 1:29
• OK, I will try... – n55 Jul 1 '15 at 1:36