0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\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$ Sep 4, 2017 at 9:48
  • $\begingroup$ That makes sense, thanks! $2E$ is at least $6V$ basically, yeah. $\endgroup$
    – BMBM
    Sep 4, 2017 at 9:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .