Consequences of Euler's Formula
What You'll Learn
You'll learn how to derive the fundamental edge inequality E ≤ 3V - 6 that every simple planar graph must satisfy.
The Core Idea
Euler's formula (V - E + F = 2) gave us a beautiful relationship connecting vertices, edges, and faces. Now we'll squeeze even more information out of it to discover a powerful upper bound on how many edges a planar graph can have.
Think of it like a building code: just as zoning laws limit how tall buildings can be based on their footprint, planarity imposes strict limits on how "dense" with edges a graph can be given its number of vertices.
Deriving E ≤ 3V - 6
Start with a simple planar graph (no loops, no multiple edges) having at least 3 vertices. Every face must be bounded by at least 3 edges. If we count edge-face incidences, each edge borders exactly 2 faces, giving us:
2E ≥ 3F
Why? The sum of all face boundaries counts each edge twice (once from each side), and this sum must be at least 3F since each face needs at least 3 edges.
Rearranging: F ≤ 2E/3
Now substitute into Euler's formula:
- V - E + F = 2
- V - E + (something ≤ 2E/3) ≤ 2
- V - E + 2E/3 ≤ 2
- V - E/3 ≤ 2
- V - 2 ≤ E/3
- E ≤ 3V - 6
This inequality is sharp: some planar graphs (like K₄, the complete graph on 4 vertices) achieve it exactly!
Applications
This immediately proves K₅ isn't planar: it has V = 5, E = 10, but 3(5) - 6 = 9 < 10. Busted!
Key Takeaway: Every simple planar graph with V ≥ 3 satisfies E ≤ 3V - 6, giving us a quick planarity test by counting vertices and edges alone.