📂Graph Theory

Simple Properties of Planar Graphs

Theorem ¹

Assume that $G$ is a simple planar graph.

• [1]: If $G$ is a connected graph with $n \ge 3$ vertices and $m$ edges, then $m \le 3n - 6$
• [2]: Every simple planar graph $G$ has at least one vertex $v \in V(G)$ with $\deg v \le 5$.

Proof

[1]

Let’s assume every face of a planar graph is surrounded by at least three edges.

For the simplest case, if there is just one complete graph $K_{3}$, with edges $m=3$ and faces $f=2$, for one more face to be added, at least two more edges are needed, thus $3f \le 2m$.

Euler’s formula: For a connected planar graph $G$, let $n:=|V(G)|$, $m:=|E(G)|$, and $f$ be the number of faces, $$ n-m+f=2 $$

Following Euler’s formula, since $f = m - n + 2$, $$ 3(m-n+2) \le 2m $$ we obtain that $m \le 3n - 6$.

■

[2]

$G$ does not need to be connected, but it suffices to check each component. Without loss of generality, assume $G$ is a connected graph with at least $3$ vertices. To use reductio ad absurdum, assume every vertex of $G$ has degree at least $6$.

If the number of vertices of $G$ is $n \ge 3$ and the number of edges is $m$, since every vertex degree is at least $6$, $$ 6n \le 2m $$ Dividing both sides by $2$ gives $3n \le m$, but according to Summary [1], $$ 3n \le 3n - 6 $$ This is a contradiction, so there must be at least one vertex $v \in V(G)$ with $\deg v \le 5$.

■