Mathematics
Planar Graphs and Euler's Formula for Polyhedra
Quick fact
Euler's formula famously states that for any convex polyhedron (or any connected planar graph), V - E + F = 2. This single equation has powerful consequences, such as proving that a planar graph can have at most 3V - 6 edges, which can be used to show that K5 and K3,3 are not planar.
Why this is interesting
You've seen maps with many countries, but can you always draw them without edges crossing? What does that have to do with a simple arithmetic relation?
Read the full explanation
Understanding Planar Graphs and Euler's Formula for Polyhedra
Think of a planar graph as a network of nodes (vertices) and links (edges) drawn on a flat piece of paper so that no two links cross. When you draw such a graph, it divides the paper into regions, called faces. The outer unbounded region is also counted as a face. For any connected planar graph, no matter how complicated, the number of vertices (V), edges (E), and faces (F) always satisfy the equation V - E + F = 2. Try it with a simple triangle: V=3, E=3, F=2 (the inner triangle and the outer face), and 3 - 3 + 2 = 2. Add a vertex and connect it to two existing vertices: V=4, E=5, F=3, and 4 - 5 + 3 = 2. The formula is robust because every time you add a new edge that does not cross another, you either add a new vertex and no new face, or add a new edge and one new face, keeping the balance intact.
A deeper explanation
Why does this formula always hold? The key is that a planar graph is essentially a polyhedron flattened onto a plane. If you take a convex polyhedron and 'stretch' one face open, you get a planar graph where all faces are now internal. The same combinatorial count applies. The deeper mechanism is topological: the Euler characteristic, defined as V - E + F, is an invariant for any surface. For the sphere, it is 2. Since the plane acts like a sphere when you add a point at infinity, the invariant is 2. This invariant is powerful because it doesn't change under continuous deformations, so it holds for all planar embeddings of the same graph. Moreover, using the fact that each edge borders two faces and each face has at least three edges, we can derive that 3F ≤ 2E, and combining with Euler's formula gives E ≤ 3V - 6 for simple planar graphs (V ≥ 3). This inequality immediately shows that K5 (with 10 edges and V=5) cannot be planar, because 10 9. Such bounds are the starting point for many graph-theoretic proofs and lead to the famous Four Color Theorem.