Explain proof by contradiction of every planar graph has a node with deg at most 5

794 Views Asked by At

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

1

There are 1 best solutions below

2
On BEST ANSWER

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