The Answer to the Question
is below this banner.
Here's the Solution to this Question
Let v is number of vertices, e is number of edges.
If every vertex had degree at least 6, then the sum of the vertex degrees is at least 6v. But since the sum of the vertex degrees equals 2e , by the Handshake Lemma, we have contradicting the fact that (by Theorem).
Suppose a connected planar graph has vertices and edges.
Proof. By definition, a connected graph is planar iff it has a planar embedding. So
suppose a connected graph with v vertices and e edges has a planar embedding
with f faces. Every edge is traversed exactly twice by the face boundaries. So the sum of the lengths of the face boundaries is exactly 2e. Also, when , each face boundary is of length at least three, so this sum is at least 3f . This implies that
But by Euler’s formula, and substituting gives