3.5d Planar Graphs

Planar Graphs

A planar graph is a graph that can be drawn in the plane without any edges crossing. For any connected planar graph, Euler’s formula holds, such that
$v+f=e+2,$
where $v$ is the number of vertices, $e$ is the number of edges, and $f$ is the number of regions (or faces) into which the plane is divided by the graph, including the unbounded exterior face.

Intuition

We can prove Euler’s formula by induction on $e$:
Base Case: The formula holds when $e=0⟹v,f=1$.
Hypothesis: Assume the theorem holds for $e>0$.
Inductive Step: split in cases.

• In the case of a connected and acyclic graph (a tree), we know that it has $e=v-1$ edges. Since a tree does not form any cycles, $f=1$, and therefore Euler’s formula holds.
• In the case of a connected graph with at least one cycle, find a cycle and delete one of the edges. This reduces both $e$ and $f$ by 1, but keeps $v$ constant. Find a cycle and delete one of the edges until the graph becomes a tree. Since Euler’s formula holds for trees, by induction it also holds for all connected planar graphs.

We see that the core idea of Euler’s formula is that for every removed edge that otherwise forms a cycle, the amount of faces decreases by one.

Properties

For any planar graph, ${\sum }_{i=1}^f{s}_i=2e$.

(Upper Bound of Planarity) Planar graphs have at most $3v-6$ edges.

We start by observing that a face of a graph may have 3 edges at minimum: $s_i\ge 3(\forall i)$. We can then express ${\sum }_{i=1}^f{s}_i=2e$ as $3f\le 2e$, where $3f$ is the minimum number of total sides for all faces in a graph. Plugging in Euler’s formula, this leads us to $e\le 3v-6$.

(Kuratowski’s Theorem) A graph is non-planar if and only if it contains a $K_5$ or $K_{3,3}$.

For the case of $K_5$, since $4\le e\le 9$, and a complete graph of 5 vertices contains $\frac{5(5-1)}{2}=10$ edges (see 3.1), the planarity test does not hold.

However, the bipartite $K_{3,3}$ has $3\times 3=9$ edges, and therefore it passes the planarity test. Let’s visualize this graph, also known as “Three Wells, Three Houses”:

\begin{document}
\begin{tikzpicture}
    % Draw houses (top row)
    \node (A) at (0, 2) [draw, circle, inner sep=2] {A};
    \node (B) at (2, 2) [draw, circle, inner sep=2] {B};
    \node (C) at (4, 2) [draw, circle, inner sep=2] {C};
    
    % Draw wells (bottom row)
    \node (X) at (0, 0) [draw, circle, inner sep=2] {X};
    \node (Y) at (2, 0) [draw, circle, inner sep=2] {Y};
    \node (Z) at (4, 0) [draw, circle, inner sep=2] {Z};
    
    % Draw edges (showing crossing lines)
    \draw (A) -- (X);
    \draw (A) -- (Y);
    \draw (A) -- (Z);
    
    \draw (B) -- (X);
    \draw (B) -- (Y);
    \draw (B) -- (Z);
    
    \draw (C) -- (X);
    \draw (C) -- (Y);
    \draw (C) -- (Z);
\end{tikzpicture}
\end{document}

As you can see, every node from the one set is connected to the other. This is because there are no triangular (3-edged) cycles in $K_{3,3}$, since that would mean that two nodes of the same set are connected. So, ${\sum }_{i=1}^f{s}_i=2e$ actually becomes $4f\le 2e$. Plugging this into Euler’s formula, we get $e\le 2v-4$. Since Euler’s formula doesn’t hold, the graph is not planar.

Every planar graph can be colored with 5 colors.