The theorem says: every planar graph has a vertex of degree at most 5.

In another question, the proof by contradiction for that is

Suppose that there exists a planar graph with all vertices having degree at least $6$. Then by the handshake lemma, $E = 3V$. If $G$ is planar, then $E \leq 3V - 6$, a contradiction.

In general, I'm familiar with the handshake lemma:

$2E = \sum deg(v)$

What I don't understand is, why can I substitute $\sum deg(v)$ with $6V$, so that the equation becomes $2E = 6V$ and simplifies to $E = 3V$. Why can I just replace the sum with $6V$ ?


There are $V$ summands and we assume that each of them is at least $6$. Hence $2E\ge 6V$ (not $2E=6V$). This still contradicts $E\le 3V-6$.

| cite | improve this answer | |
  • $\begingroup$ Another way to see it, is to notice that (per handshaking) $\frac{2E}V$ is the average degree. From $E\le 3V-6$ we conclude that $\frac{2E}V\le 6-\frac{12}V<6$ and hence certainly at least once $\deg(v)<6$. $\endgroup$ – Hagen von Eitzen Sep 4 '17 at 9:48
  • $\begingroup$ That makes sense, thanks! $2E$ is at least $6V$ basically, yeah. $\endgroup$ – Max Sep 4 '17 at 9:54

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.