# Minimum Degree Bound for Simple Planar Graph

Jump to navigation
Jump to search

## Theorem

Let $G$ be a simple connected planar graph.

Then:

- $\map \delta G \le 5$

where $\map \delta G$ denotes the minimum degree of $G$.

## Proof

Aiming for a contradiction, suppose:

- $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 3 n$

That contradicts the Linear Bound Lemma.

$\blacksquare$