Planar graphs and Euler's formula: QCE General Mathematics Unit 4 Graphs and networks

What this dot point is asking

A planar graph is a graph that can be drawn on a flat surface with no edges crossing. When it is drawn that way, its edges divide the plane into regions called faces. The QCAA General Mathematics 2025 syllabus asks you to understand these two ideas and to apply Euler's formula,

where $v$ is the number of vertices, $f$ the number of faces and $e$ the number of edges, to solve problems about planar graphs. This sits in Topic 3, Graphs and networks, sub-topic "Planar graphs, paths and cycles".

Euler's formula questions are usually short and simple familiar (find the missing number), but they are also used inside larger problems: checking that a network diagram has been drawn correctly, working with degree sums, or deciding whether a layout can be built without crossings.

The answer

Planar graphs and redrawing

A graph is planar if it can be drawn with no edges crossing, even if the drawing you have been given has crossings. Vertices can be moved and edges can be bent (they do not have to be straight) as long as the same vertices stay joined by the same edges.

The classic example is the complete graph on four vertices. Drawn as a square with both diagonals, two edges cross. Move one vertex into the middle of the triangle formed by the other three, and every edge can be drawn without crossing. So it is planar.

Some graphs cannot be redrawn without crossings however hard you try; these are non-planar. The complete graph on five vertices (every one of five vertices joined to every other) is the smallest example. You are not required to prove non-planarity in General Mathematics, but you should know that not every graph is planar.

Faces

When a planar graph is drawn without crossings, the edges divide the plane into faces. Always count the outer (unbounded) face, the region surrounding the whole graph. In the redrawn graph above there are three small triangular faces inside and one outer face, so $f = 4$.

Useful special cases:

• A tree (connected, no cycles) encloses nothing, so it has only the outer face: $f = 1$.
• A single cycle has two faces: the inside and the outside.
• Every time you add an edge that joins two existing vertices without crossing, you split a face into two: $f$ increases by 1.

Euler's formula

For any connected planar graph, drawn without crossings,

Check it on the redrawn graph: $v = 4$, $f = 4$, $e = 6$, and $4 + 4 - 6 = 2$.

Why is it always 2? Start with a single vertex: $v = 1$, $f = 1$ (the outer face), $e = 0$, so $v + f - e = 2$. Build any connected planar graph by adding one edge at a time. An edge to a new vertex increases $v$ and $e$ by 1 each, so $v + f - e$ is unchanged. An edge between two existing vertices splits a face, increasing $f$ and $e$ by 1 each, so again $v + f - e$ is unchanged. It starts at 2 and never changes.

Using the formula

Most questions give two of $v$, $e$ and $f$ and ask for the third:

• $v = 8$, $e = 12$: $f = 2 - 8 + 12 = 6$.
• $v = 7$, $f = 5$: $e = 7 + 5 - 2 = 10$.
• $e = 14$, $f = 8$: $v = 2 - 8 + 14 = 8$.

Sometimes $e$ is hidden in information about degrees. Since each edge has two ends, the sum of the degrees of all the vertices is $2e$. A connected planar graph with 10 vertices, each of degree 3, has $e = \frac{10 \times 3}{2} = 15$ edges, and then $f = 2 - 10 + 15 = 7$.

Checking a drawing

Euler's formula is also a quick check. If a question gives a planar graph and your counts do not satisfy $v + f - e = 2$, you have miscounted (most often by forgetting the outer face, or by counting a crossing point as a vertex). Crossing points in a drawing are not vertices; if a drawing has crossings, redraw it first or you will count the faces wrongly.

Practical contexts

• Circuit boards and flat wiring. Connections printed on one layer of a board cannot cross, so the circuit must form a planar graph.
• Maps and regions. Tracks, roads or borders form the edges, junctions form the vertices, and the regions (including the area outside) are the faces.
• Utilities. The famous puzzle of connecting three houses to three utilities without any lines crossing is impossible because that graph is non-planar.