Euler Formula and Applications

Euler's formula $n - m + f = 2$ for planar graphs provides powerful constraints on graph structure, leading to edge bounds and planarity tests.

TheoremEuler's Formula for Planar Graphs

For any connected planar graph with $n$ vertices, $m$ edges, and $f$ faces: $n - m + f = 2$

For disconnected graphs with $k$ components: $n - m + f = k + 1$ .

ProofProof by Induction

Induct on $m$ . Base: $m=0$ gives $n$ isolated vertices, $f=1$ outer face, so $n - 0 + 1 = n+1 = k+1$ ✓.

Inductive step: Remove an edge $e$ . If $e$ is a bridge, it reduces components by 1 and faces stay same: $(n) - (m-1) + f = k$ becomes $n - m + f = k+1$ after restoring $e$ . If $e$ is not a bridge, it merges two faces: $(n) - (m-1) + (f-1) = 2$ gives $n - m + f = 2$ ✓.

■

TheoremEdge Bounds for Planar Graphs

For a connected planar graph with $n \geq 3$ vertices and $m$ edges:

$m \leq 3n - 6$ (general bound)
If no triangles: $m \leq 2n - 4$ (bipartite bound)

These bounds immediately prove $K_5$ and $K_{3,3}$ are non-planar.

Example$K_5$ is Non-Planar

$K_5$ has $n=5$ vertices and $m=10$ edges. If planar, $m \leq 3n - 6 = 9$ . But $10 > 9$ , contradiction. Thus $K_5$ cannot be planar.

Similarly, $K_{3,3}$ is bipartite with $n=6$ , $m=9$ . Bipartite bound gives $m \leq 2(6) - 4 = 8 < 9$ , so $K_{3,3}$ is non-planar.

DefinitionAverage Face Degree

In a planar graph, each face $i$ has degree $d_i$ (number of edges bounding it). Then: $\sum_{i=1}^f d_i = 2m$ This double-counts edges: each edge bounds two faces (or one face twice if a bridge).

Remark

Euler's formula extends to surfaces: on a surface of genus $g$ (sphere has $g=0$ , torus $g=1$ ), the formula becomes: $n - m + f = 2 - 2g$ This Euler characteristic is a topological invariant, connecting graph theory to algebraic topology.