Planar Graphs and Euler's formula
A planar graph can be drawn so that no two edges cross, and it then splits the page into faces, including the outside face. For any connected planar graph, Euler's formula links the counts: \(v-e+f=2\). In NSW Year 10 Advanced maths you redraw graphs in planar form, count vertices, edges and faces, and find a missing value from the formula (NESA outcome MA5‑NET‑P‑01).
You will use \(v-e+f=2\) to find edges, faces or vertices, check it on wheels, prisms and cube networks, and redraw graphs so no edges cross. You will model the borders of Australia's mainland states and territories, find the vertices of an icosahedron, and see what happens when the graph is not connected. Harder questions show that \(e\le3v-6\) and why the three-utilities puzzle cannot be drawn flat. It is part of Year 10 Advanced Networks.
Theory
A planar graph can be drawn with no edges crossing. For every connected planar graph, Euler's formula \(v - e + f = 2\) links the vertices, edges and faces, where the outside region counts as a face. This Year 10 Advanced maths page covers counting faces, redrawing without crossings, solids, solving for an unknown and proving a graph is not planar.
A graph is planar if it can be drawn on a flat page so that no two edges cross. A drawing with crossings may still be of a planar graph, if it can be redrawn without them. A graph that can never be drawn without a crossing is non-planar.
A planar drawing divides the page into regions called faces. The unbounded region outside the drawing is also a face, so every planar drawing has at least one face.
Euler's formula: for a connected planar graph with \(v\) vertices, \(e\) edges and \(f\) faces, \(v - e + f = 2\). The graph must be connected (in one piece) and drawn with no crossings.
The corners and edges of a solid such as a prism or a pyramid can be drawn flat as a planar graph, so Euler's formula also holds for many solids, with \(f\) the number of faces of the solid.
They lead into the networks topics of Standard maths in Years 11 and 12.
| To find | Rearranged |
|---|---|
| \(v\) | \(v = 2 + e - f\) |
| \(e\) | \(e = v + f - 2\) |
| \(f\) | \(f = 2 - v + e\) |
Using Euler's formula
- Check that the drawing has no crossings and is in one piece. If edges cross, redraw first.
- Count \(v\) and \(e\). Tick the edges off as you count so none is missed.
- Count \(f\): the enclosed regions plus \(1\) for the outside. An edge sticking out into a face does not make a new face.
- Check \(v - e + f = 2\), or substitute the two known values to find the third.
Other question types
- Redrawing: move one crossing edge to the outside of the figure as a curve, or drag a vertex to a new position. The vertices and which pairs are joined must not change.
- Maps: make each region a vertex and join two vertices when the regions share a border (not just a corner). Count the edges, then use Euler's formula for the faces.
- Solids: the faces of the solid are the faces of its network. If every face has \(k\) edges, \(e = \dfrac{k\times f}{2}\). If every vertex has degree \(d\), \(e = \dfrac{d\times v}{2}\).
- Changing a graph: work out how \(v\), \(e\) and \(f\) each change. For example, putting a new vertex in the middle of an edge adds \(1\) to \(v\) and \(1\) to \(e\), and leaves \(f\) alone, so \(v - e + f\) stays the same.
- Families of graphs: write \(v\), \(e\) and \(f\) as expressions in the pattern number, then simplify \(v - e + f\).
- Not planar? Substitute into an inequality such as \(e \le 3v - 6\), or combine Euler's formula with a face count, and look for a contradiction (Example 4).
Vertices: \(A\) to \(G\), so \(v = 7\).
Edges: \(6\) around the hexagon, \(AC\) and \(AE\), and \(DG\), so \(e = 9\).
Faces: triangles \(ABC\) and \(AEF\), quadrilateral \(ACDE\), and the outside, so \(f = 4\). The edge \(DG\) sticks out into the outside face and does not enclose a new region.
| \(v - e + f\) | \(=\) | \(7 - 9 + 4\) |
| \(\) | \(=\) | \(\mathbf{2}\ \checkmark\) |
(i) Show that it is planar.
(ii) Find \(v\), \(e\) and \(f\).
(i) Move one of the crossing edges. Keep \(AC\) inside the rectangle and redraw \(BD\) as a curve around the outside of \(C\) (right). The edges still join the same vertices, and now nothing crosses, so the graph is planar.
(ii) \(v = 5\) and \(e = 8\): redrawing never changes these. Count the faces in the planar drawing: \(EAB\), \(ABC\), \(ACD\), the region between \(BC\), \(CD\) and the curve, and the outside.
| \(f\) | \(=\) | \(\mathbf{5}\) |
| \(v - e + f\) | \(=\) | \(5 - 8 + 5 = 2\ \checkmark\) |
You cannot count faces in the drawing with the crossing: Euler's formula only applies to a drawing with no crossings.
Count the edges around every face, then halve, because each edge has been counted twice.
| \(12\times 5\) | \(=\) | \(60\) |
| \(e\) | \(=\) | \(\dfrac{60}{2} = \mathbf{30}\) |
Euler's formula also holds for the corners, edges and faces of a solid like this, because its network can be drawn flat.
| \(v - 30 + 12\) | \(=\) | \(2\) |
| \(v\) | \(=\) | \(\mathbf{20}\) |
Check with degrees: \(3\) edges meet at each corner, and \(20\times 3 = 60 = 2\times 30\).
(i) Show that the complete graph on \(5\) vertices is not planar.
(ii) Can a planar graph of this kind have \(8\) vertices and \(20\) edges?
(i) Every pair of the \(5\) vertices is joined, so \(e = \dfrac{5\times 4}{2} = 10\).
| \(3v - 6\) | \(=\) | \(3\times 5 - 6 = 9\) |
A planar graph with \(5\) vertices has at most \(9\) edges, but this one has \(10\). So it is not planar: however it is drawn, some edges cross.
(ii)
| \(3v - 6\) | \(=\) | \(3\times 8 - 6 = 18\) |
\(20 \gt 18\), so no.
The test works in one direction only. If \(e \gt 3v - 6\), the graph is not planar. If \(e \le 3v - 6\), the graph might still be non-planar, so try to draw it or use another argument.
Common pitfalls
Frequently asked questions
What is Euler's formula for planar graphs?
For a connected planar graph, \(v - e + f = 2\), where \(v\) is the number of vertices, \(e\) the number of edges and \(f\) the number of faces. The outside region counts as one of the faces.
What is a planar graph?
A planar graph is one that can be drawn on a flat surface with no two edges crossing. A drawing with crossings can still show a planar graph if it can be redrawn without them.
Does the outside count as a face?
Yes. The unbounded region outside the drawing is always counted as a face. A single triangle has 2 faces: the inside and the outside.
How do you show a graph is not planar?
One way is to count its vertices and edges. A connected planar graph with at least \(3\) vertices and no loops or repeated edges has \(e \le 3v - 6\), so a graph with more edges than that cannot be planar.
Does Euler's formula work for 3D solids?
Yes, for solids such as prisms, pyramids and the regular polyhedra. Their corners, edges and faces can be flattened into a connected planar graph, so vertices minus edges plus faces equals 2.