2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.