So, by an informal proof I can show this is true: i. e., by creating a connected planar graph with $6$ nodes with one node of degree $5$, and $5$ nodes of degree $1$. Then by adding edges to a node with currently degree $1$, I can increase that node to degree $5$, eventually there will be a point where I can no longer add any edges without breaking the condition of planarity. And will have remaining nodes with degree no more than $5$.
Is there a better way to approach this? Perhaps with Euler's Theorem which states that a planar graph will satisfy the following condition: $V – E + R = 2$, where $v$ is vertices; $e$ is edges; $r$ is regions and we know that sum of all vertex degrees is equivalent to $2E$.
Best Answer
Yes, Euler's formula is a good start. So, $n - m + f = 2$ for any connected non-trivial planar graph $G$, where $n$ is the number of vertices, $m$ is the number of edges and $f$ is the number of faces. If $G$ is a tree than it obviously has a leaf that is a vertex of degree $1$. If $G$ contains a cycle, then each edge belongs to at most $2$ faces, while each face contains at least $3$ edges, so $3f \le 2m$ that is $f \le \frac23 m$. Then $n - m + f + \frac23 m \ge 2 + f$, therefore $3n - 6 \ge m$.
Also by handshake lemma we have $\sum_{v \in V(G)} \deg v = 2m$. So if $\deg v \ge 6$ for all $v \in V(G)$, then $6n - 12 \ge 2m \ge 6n$. This contradiction shows that there is a vertex of degree at most $5$.