V - E + F = 2, Kuratowski's theorem, and why planarity matters
Count the vertices, edges, and faces of any flat drawing and one number never changes. That single rule limits how crowded a planar graph can get.
Step through the graphs and check that V - E + F comes out to 2 every time. Press Show Faces to see which regions count, including the outer one.
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.
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.
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.
For each graph, decide Planar or not, then move on with Next. Look for a hidden copy of K5 or K3,3 -- finding one means the graph can never lie flat.
For each graph, decide whether it is planar or not. After answering, non-planar graphs will highlight a forbidden K5 or K3,3 subdivision.
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.
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.
Click one vertex and then another to add an edge, and watch the count climb toward the 3V - 6 limit. Turn on Triangle-Free to see the tighter 2V - 4 limit.
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.
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).
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.
Planar graphs have at most 3V - 6 edges -- they are "sparse" compared to general graphs, which can have up to V(V-1)/2 edges.
This sparsity guarantees every planar graph has a vertex of degree at most 5, a crucial fact for coloring proofs -- it means we can always find a vertex to remove during an inductive argument.
Spot a mistake or have an idea?