V - E + F = 2, Kuratowski's theorem, and why planarity matters
Euler's formula V - E + F = 2 is one of the most fundamental results about planar graphs. It tells us that for any connected planar graph, the number of vertices minus the number of edges plus the number of faces (including the unbounded outer face) always equals 2. This elegant identity constrains how complex a planar graph can be and gives us powerful tools to prove the four color theorem.
From Euler's formula we can derive tight bounds on the number of edges a planar graph can have, characterize which graphs are planar by their forbidden subgraphs, and ultimately show that every planar graph must contain a vertex of low degree -- the key structural fact that makes coloring arguments work.
Step through a series of planar graphs and verify that Euler's formula holds in each case. Watch how the counts of vertices, edges, and faces change while the alternating sum V - E + F stays fixed at 2.
Cycle through the preset graphs to see Euler's formula V - E + F = 2 hold for each connected planar graph. Toggle face highlighting to see how the edges divide the plane into regions.
Key insight: For any connected planar graph, V - E + F = 2. This identity constrains the structure of planar graphs and is the foundation for proving results like the five color theorem.
Not every graph can be drawn in the plane without crossings. Kuratowski's theorem gives a complete characterization: a graph is planar if and only if it contains no subdivision of K5 or K3,3. Test your intuition by classifying each graph below.
For each graph, decide whether it is planar or not. After answering, non-planar graphs will highlight a forbidden K5 or K3,3 subdivision.
Key insight: Kuratowski's theorem says a graph is planar if and only if it contains no subdivision of K5 or K3,3. These are the two "minimal" non-planar graphs.
Euler's formula directly implies that a planar graph cannot have too many edges. For a planar graph with V vertices, there can be at most 3V - 6 edges (or 2V - 4 if the graph is triangle-free). Build a graph below and watch as you approach the maximum.
Click a vertex to select it, then click another vertex to add an edge between them. Watch the edge count approach the maximum allowed for a planar graph. Toggle triangle-free mode to see the stricter bound of 2V - 4.
Key insight: A planar graph on V vertices has at most 3V - 6 edges. This means planar graphs are sparse -- they cannot have too many connections, which is why they can always be colored with few colors.