1
$\begingroup$

I have to prove that in a graph $G$ with $n$ vertices and $n$ edges which has no isolated or pendant vertices, every vertex has degree 2.

Now I know that $$\sum_{v\in V} d(v)=2|E|=2n$$

but I suppose I also have to prove every vertex has same degree and I'm not sure how to do that.

Improve this question
$\endgroup$
  • $\begingroup$ What is a "pendant" vertex? $\endgroup$ – JMoravitz Sep 14 '17 at 19:45
  • $\begingroup$ @JMoravitz Presumably of degree 1. $\endgroup$ – Théophile Sep 14 '17 at 19:45
3
$\begingroup$

Hint: From the equation you gave, we can divide both sides by $n$ to get the average degree:

$$\frac1n \sum_{v\in V} d(v)=2$$

Now, if any vertex has a degree greater than the average, there must necessarily be another vertex with a degree lower than the average. What does that imply?

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ Makes sense, thanks! $\endgroup$ – Stefan Stipanovic Sep 14 '17 at 19:47
  • $\begingroup$ The logic should go the other way (if pendant then there exists a vertex with degree greater than 2), but the core idea is excellent. $\endgroup$ – David G. Stork Sep 14 '17 at 19:49
  • $\begingroup$ @DavidG.Stork Thank you! I think the logic is solid, though: we know from the outset that there are no isolated or pendant vertices, so the only other possibility is if there is a vertex of degree greater than 2, which leads to a contradiction. $\endgroup$ – Théophile Sep 14 '17 at 20:18

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.