Euler's formula for planar graphsAQA A-Level Further Maths: Revision notes

A graph is planar if it can be drawn in the plane with no edges crossing. A planar drawing divides the plane into regions called faces. The unbounded region outside the graph is also a face, called the outer face, and it always counts. Count faces from a drawing without crossings, not from a drawing where edges cross. A tree (connected, with no cycles) has $e=v-1$ and just one face, the outer face, because it encloses nothing.

For a connected planar graph with $v$ vertices, $e$ edges and $f$ faces (including the outer face): $v-e+f=2.$ Given any two of $v$, $e$, $f$ you can find the third. Example: $8$ vertices and $12$ edges give $f=2-8+12=6$. Rearranged: $e=v+f-2$ and $v=2+e-f$.

Euler's formula shows how changes affect the count of faces.

• Adding a new vertex joined by one edge changes $v$ and $e$ by $1$ each, so $f$ is unchanged.
• Adding an edge between two existing vertices (without crossings) splits a face in two, so $f$ increases by $1$.
• Subdividing an edge adds one vertex and one edge, so $f$ is unchanged. Example: start with $v=9$, $e=15$, $f=8$. Add two pendant vertices and one further edge: $v=11$, $e=18$, and $11-18+f=2$ gives $f=9$.

The degree of a face is the number of edges around its boundary. Each edge has two sides, and each side lies in a face, so $\text{sum of the face degrees}=2e.$ This works with Euler's formula. If all $f$ faces have degree $3$, then $3f=2e$. Combined with $v-e+f=2$ and $v=7$: $7-e+\frac{2e}{3}=2$, so $e=15$ and $f=10$. In a simple graph (no loops or multiple edges) every face has degree at least $3$, so $2e\ge3f$. This gives a contradiction when the numbers do not fit: with $v=12$, $e=31$ we get $f=21$ and $3f=63>62=2e$, so no such planar graph exists.