Minimum Degree Bound for Simple Planar Graph
Let $G$ be a simple connected planar graph. Then:
- $\map \delta G \le 5$, where $\delta$ is the minimum degree of a graph.
Proving by contradiction. Consider the counter hypothesis:
- $G$ is a simple planar graph and $\map \delta G \ge 6$.
Let $m$ and $n$ denote a number of edges and vertices respectively in $G$.
Then, by the Handshake Lemma:
- $m \ge 3n$
That contradicts the Linear Bound Lemma.