Planar Graph

Definition (Planar Embedding)

A Planar Embedding of a Graph $G$ is a drawing in the plane without crossing any edges. For example,

graph
	subgraph R^2; 
		a((a))
		b((b))
		c((c))
		d((d))
	end
	a o--o b;
	c o--o b;
	d o--o a;
	c o--o a;
	c o--o d;

has a planar embedding. A graph $G$ is planar if it has a planar embedding.

Definition (Planar Faces)

Given a planar embedding of some graph $G$, this was split the plane into faces, the connected regions of the ${\mathbb{R}}^2\setminus G$.

For example, in the graph above, we have region $acd,abc$, and the ambient space.

Example Planar Graphs

We have the following table:

Graph	Faces	Vertices	Edges	Faces - Edges + Vertices
Tree	$1$	$n$	$n-1$	$2$
Cycle	$2$	$n$	$n$	$2$
Wheel	$n+1$	$n+1$	$2n$	$2$
Grid with $n\times n$ squares	$n^2+1$	$(n+1{)}^2$	$2n(n+1)$	$2$

Euler’s Formula

If $G$ is a finite, connected planar graph, then any planar embedding has

$$|F|-|E|+|V|=2$$

where $F$ is the set of faces formed by $G$.

Proof: We prove by induction on $|E|$.

Base Case: $|E|=|V|-1$. By Lemma (Tree Edge Count), this is a tree. We are done

Assume that any graph with fewer edges and the same number of vertices satisfies Euler’s Formula. If $|E|<|V|$, then $G$ is not connected, a contradiction. If $|E|\ge |V|$ then $G$ is not a tree and has a cycle $C$ and some edge $e\in C$.

Consider

$$G^{\prime }=G-\{e\}$$

Then

• $|V(G)|=|V(G^{\prime })|$
• $|E(G)|=|E(G^{\prime })|+1$
• $|F(G)|=|F(G^{\prime })|+1$ because when remove $e$, we “open up” the cycle and merge two faces together. By the induction hypothesis,

$$\begin{array}{rl}|V(G)|-|E(G)|+|F(G)|& =|V(G^{\prime })|-(|E(G^{\prime })|+1)+(|F(G^{\prime })|+1)\\ & =|V(G^{\prime })|-|E(G^{\prime })|+|F(G^{\prime })|\\ & =2\end{array}$$

and we are done.

Theorem (Planar Graph Edge Bound)

If $G$ is a connected Planar Graph with $|V|\ge 3$, then

$$|E|\le 3|V|-6$$

Proof: By Euler’s Formula, and lemma , we have

$$2=|V|-|E|+|F|\le |V|-|E|+\frac{2|E|}{3}=|V|-\frac{|E|}{3}$$

Rearranging, we get $|E|\le 3|V|-6$.

Equality is achieved iff all faces are triangles.

Theorem ($K_5$ is Non-Planar)

The Complete Graph $K_5$ is non-planar.

Proof: If it was, then by Theorem (Planar Graph Edge Bound),

$$10=|E|\le 3|V|-6=9$$

a contradiction.

Theorem ($K_{3,3}$ is Non-Planar)

The complete bipartite graph $K_{3,3}$ is non-planar.

Proof: Since it is bipartite, it has no odd cycles by Theorem (Bipartite Cycles). Therefore if it was planar, then any face has at least $4$ sides. Thus, by Theorem (Planar Graph Edge Bound),

$$9=|E|\le 2|V|-4=8$$

a contradiction.

Theorem (Planar Graphs have Bounded Minimum)

If $G$ is a finite, connected planar graph, then $G$ has minimum Degree $\delta (G)\le 5$.

Proof: Otherwise, $\delta (G)\ge 6$. Then by Handshake Lemma,

$$2|E|=\sum _{v\in V}\mathrm{deg}(v)\ge 6|V|$$

such that $|E|\ge 3|V|$. But then

$$3|V|-6\ge |E|\ge 3|V|$$

by Theorem (Planar Graph Edge Bound) which is a contradiction.

Lemma (Triangulations)

For nay planar embedding of a graph $G$ there is a way to add more edges to $G$ to get a new planar graph $G^{\prime }$ in which all faces are triangles.