# A loop-free connected planar (simple) graph has at least one node of degree no more than 5 (True/False).

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

• Thanks I forgot I can utilize Kuratowski's theorem, the $K_5$ minor is good insight – Diante Apr 8 '17 at 0:44
• I don't see obvious ways to get a $K_5$ minor here, and it's certainly not going to follow from all nodes having degree $5$: what about the icosahedron? Euler's formula is a better approach. – Misha Lavrov Apr 8 '17 at 0:58

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