Consequences of Euler's Formula

Graph Theory · Axiom Academy

LESSON Consequences of Euler's Formula Powerful inequalities and applications derived from V - E + F = 2 Theorem: If G is a simple planar graph with V ≥ 3 vertices, then E ≤ 3V - 6. 2. Triangle-Free Bound: E ≤ 2V - 4 Theorem: If G is a simple planar graph with V ≥ 3 vertices and no triangles (girth ≥ 4), then E ≤ 2V - 4. Application: This bound is crucial for proving K₃,₃ is non-planar. K₃,₃ has no triangles (it's bipartite), V = 6, E = 9. But 9 > 2(6) - 4 = 8, contradiction! 3. Every Planar Graph Has Low-Degree Vertex Theorem: Every planar graph has a vertex of degree at most 5. Corollary: The average degree in a planar graph is strictly less than 6. This is fundamental for graph coloring algorithms! These inequalities give us practical tools to prove graphs are non-planar without attempting to draw them. • K₅ has V = 5 vertices and E = 10 edges • If K₅ were planar: E ≤ 3V - 6 = 3(5) - 6 = 9 • K₃,₃ has V = 6 vertices and E = 9 edges • General bound gives: E ≤ 3V - 6 = 12 ✓ (not helpful) • But K₃,₃ is bipartite → no triangles! • Triangle-free bound: E ≤ 2V - 4 = 2(6) - 4 = 8 • Therefore K₃,₃ is not planar. Theorem: Every planar graph can be colored with at most 5 colors such that no two adjacent vertices have the same color.

This is the written version of the interactive lesson above. See the full Graph Theory course.