# Minimum Degree Bound for Simple Planar Graph

Jump to: navigation, search

## Theorem

Let $G$ be a simple connected planar graph. Then:

$\map \delta G \le 5$, where $\delta$ is the minimum degree of a graph.

## Proof

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.

$\blacksquare$