Euler's Formula for Planar Graphs
What you'll learn: You'll master Euler's formula V - E + F = 2, which reveals a beautiful relationship between vertices, edges, and faces in any connected planar graph.
The Core Idea
Euler's formula states that for any connected planar graph:
V - E + F = 2
where:
- V = number of vertices
- E = number of edges
- F = number of faces (including the outer, unbounded face)
This remarkable formula tells us that these three quantities aren't independent—they're locked together in a fixed relationship. No matter how you draw your planar graph, as long as it's connected, this equation always holds.
Understanding Through Example
Consider a triangle drawn in the plane:
- V = 3 vertices
- E = 3 edges
- F = 2 faces (the interior region and the exterior unbounded region)
Check: 3 - 3 + 2 = 2 ✓
Now consider a square:
- V = 4 vertices
- E = 4 edges
- F = 2 faces
Check: 4 - 4 + 2 = 2 ✓
Add a diagonal to the square:
- V = 4 (unchanged)
- E = 5 (added one edge)
- F = 3 (the diagonal splits the interior into two regions)
Check: 4 - 5 + 3 = 2 ✓
Why It Matters
Euler's formula is a powerful tool for:
- Proving non-planarity: If V - E + F ≠ 2, the graph cannot be planar
- Finding missing values: If you know two of V, E, F, you can calculate the third
- Establishing constraints: It helps prove important bounds (like K₅ being non-planar)
Key Takeaway: Euler's formula V - E + F = 2 is a fundamental invariant that connects the vertex, edge, and face counts of any connected planar graph, providing a simple test and powerful constraint for planar structures.