Euler's Formula

Euler's formula links the basic counts of a planar embedding: vertices, edges, and faces.

Statement (connected case)

Let $G$ be a connected plane graph with

• $V$ vertices,
• $E$ edges,
• $F$ faces (including the outer face).

Then:

$V - E + F = 2.$

Generalization (multiple components)

If the embedding has $c$ connected components, then

$V - E + F = 1 + c.$

Proof idea (one clean approach)

Take a connected plane graph.

• If it has a cycle, remove an edge on the cycle. This keeps the graph connected, decreases $E$ by $1$, and merges two faces into one, so $F$ also decreases by $1$. The quantity $V-E+F$ stays the same.
• Repeat until you reach a tree (connected and acyclic). For a tree, $E=V-1$ and $F=1$, so $V-E+F = V-(V-1)+1 = 2$.

Therefore $V-E+F$ was $2$ all along.

Standard corollaries

Edge bound for planar graphs

If a connected simple planar graph has $V \ge 3$, then

$E \le 3V - 6.$

Reason: in a triangulation, every face has at least $3$ edges and every edge borders at most $2$ faces, so $3F \le 2E$; combine with $V-E+F=2$.

Bipartite planar bound

If the graph is bipartite (so it has no triangles), then every face has length at least $4$, giving

$E \le 2V - 4.$

Quick non-planarity tests

• For $K_5$, we have $V=5$, $E=10$, but $10 > 3\cdot 5 - 6 = 9$, so $K_5$ is not planar.
• For $K_{3,3}$, we have $V=6$, $E=9$, but $9 > 2\cdot 6 - 4 = 8$, so $K_{3,3}$ is not planar.