Graph Theory - Planar graphs

Graph theory is first and foremost about combinatorics, and so graphs certainly could be thought of as abstract objects in their own right, much like groups, or vector spaces. However, their interpretation in terms of ("physical") vertices and edges is highly suggestive, and often provides us with motivation and/or a foothold for an intuitive understanding of the underlying objects.

One (combinatorial) property of graphs that would be almost impossible to dream up without this visualisation is planarity. (A graph is said to be planar if it can be embedded in the Euclidean plane without any of its edges crossing. Thus, in some sense, any planar graph corresponds to a polygonisation of the plane.¹) We can push this topologically motivated program further by defining other flavours of planarity, embedding graphs on various topological surfaces, such as the torus, or the Klein bottle. It's fascinating to take a moment to observe that, in doing so, we are forging a link between topology and combinatorics, two wildly different fields of study. The link closely involves the Euler characteristic of the surface, as we will show in a moment, and raises the question: is the Euler characteristic a topological constant, or a combinatorial one?

This post will contain a collection of results and comments concerning planar graphs. I intend to update it as I work through my notes.

Note that we need at least 3 vertices for planar graphs to become non-trivial.

A maximal planar graph corresponds to a triangulation.

This is a crucial observation. If you have any face of size (number of edges) greater than 4, you can draw in a diagonal to obtain a new graph $G^\prime$ containing $G$. Furthermore, a maximal planar graph is bridgeless, and connected. You can extend any finite planar graph to a maximal planar graph.

There are actually only two non-planar graphs (in the plane).

Every time that a graph fails to be planar, the problem can be traced back to one of two generic cases. There are only two geometric "obstacles" to planarity!


It's fairly obvious that any graph containing a non-planar subgraph can't be planar. We need to extend this concept slightly to "subdivisions". We obtain a subdivision of a graph by replacing one edge with a path of edges spanning several vertices. It's easy to see that any graph containing a subdivision of a non-planar graph can't be planar.

Two simple non-planar graphs are shown above: $K_{3,3}$ and $K_5$. From the above observations, it's immediate that any graph containing a subdivision of $K_{3,3}$ or $K_5$ is necessarily non-planar. The amazing fact is that the converse is also true, by Kuratowski's theorem: $G$ is non-planar $\Leftrightarrow$ $G$ contains a subdivision of $K_5$ or $K_{3,3}$. The proof of Kuratowski's theorem is not included in the course.

Note: To see that $K_5$, and $K_{3,3}$ are indeed non-planar, you can check that they both violate the bound on the edges in terms of the girth given below. You can also argue constructively by drawing them in a methodic fashion.

Euler's formula.

Let $G$ be a connected planar graph with $n$ vertices, $m$ edges, and $f$ faces. Consider any surface of Euler characteristic $E$. Then the following formula holds:

$$n-m+f=E$$

We give a proof for the case $E=2$, corresponding to the Euclidean plane.
Proof: We induct on $m$, for fixed $n$.
$G$ is connected, so contains a spanning tree, which has $n-1$ edges, so $m \geq n-1$.

• If $m=n-1$, then $G$ is equal to its spanning tree, so there is only one face (a tree is acyclic). Thus $n-m+f=n-(n-1)+1=2$, as required.
• If $m>n-1$, then $G$ must contain a cycle. Pick an edge $e$ of any cycle. Then $e$ separates two distinct faces. Also, $G-e$ clearly remains connected. By the induction hypothesis applied to $G-e$, $n-(m-1)+(f-1)=2$, which directly implies the required result for $G$. $\square$

Note: Euler's formula proves that the number of faces of a planar graph is independent of the way that you choose to realise its embedding in the plane (the sizes of the different faces are not!)

There are strong restrictions on the number of edges a planar graph can have.

Let $G$ be a planar graph with $n\geq 3$ vertices, and $m$ edges. Then $m \leq 3n - 6$. This is easy to prove, as when $G$ is a triangulation $2m=3f$, and the result with equality pops right out of Euler's formula (and every planar graph can be extended to a triangulation simply by adding edges).

We can be more precise by obtaining bounds on the number of edges in terms of the girth $g$ (length of the shortest cycle in the graph). Assume G is connected. If G is acyclic (a tree) the number of edges is less than the number of vertices, so assume the graph has a cycle, so that the girth $g\geq3$ is defined. Observe that $2m = \sum i f_i$, where $f_i$ is the number of faces bordered by $i$ edges. (If some face borders both sides of the same edge, we should count that edge twice.) This gives: $2m = \sum i f_i \geq gf$, allowing us to conclude that $m \leq \displaystyle \frac{g}{g-2}(n-2)$ from Euler's formula. Note that substituting $g=3$ recovers the special case obtained above by considering triangulations.

This is a remarkably strong restriction, as in general a graph can have up to $n \choose 2$ $\sim n^2$ edges. So, in some sense, most graphs contain a substructure isomorphic to either $K_{3,3}$ or $K_5$. Maybe we can conceptually draw a link to Ramsey theory here?

There is one more piece of information left to squeeze out of the above, but at this point it's hardly surprising. The minimum degree $\delta(G)$ of a graph is closely linked to the number of edges, so we can easily obtain a (strong) upper bound as a corollary. If $\delta(G) \geq 6$, then $2m \geq 6n$ by the handshaking lemma, contradicting $m \leq3n - 6$ (recall $n\geq 3$). We conclude that planar graphs must satisfy $\delta(G)\leq 5$.

---

1 This may get tricky for infinite/uncountable graphs. Something interesting to think about! See my relevant stackexchange post, which has generated a decent amount of interest.