Topic 05 — CS 70 Discrete Mathematics
Planar Graphs
& Coloring
Euler's formula is one of the most beautiful results in mathematics. We use it to prove that certain graphs can never be drawn without crossings — and then use those results to color any map on Earth with just five colors.
Planar Graphs
A graph is planar if it can be drawn in the plane such that no two edges cross. Such a drawing is called a planar embedding or planar drawing.
K₃ (Triangle)
Planar ✓
Draw as a triangle.
K₄
Planar ✓
Draw outer triangle + one internal vertex.
K₅
NOT planar ✗
Any drawing must have a crossing.
K₃,₃
NOT planar ✗
The utility graph — proven below.
Faces of a Planar Graph
A face of a planar drawing is a connected region of the plane. One face is always the unbounded outer region (the outer face or infinite face). Every other face is bounded.
Euler's Formula
For any connected planar graph with v vertices, e edges, and f faces (in any planar drawing):
Equivalently: v − e + f = 2. This is called the Euler characteristic of the plane.
For a cube: v=8, e=12, f=6. Check: 8+6 = 12+2 = 14. ✓
Proof of Euler's Formula
Claim: Every connected planar graph satisfies v + f = e + 2.
Base Case (e = 0): A connected graph with 0 edges must have exactly 1 vertex (v=1) and 1 face (the whole plane, f=1). Check: 1 + 1 = 0 + 2. ✓
Inductive Step: Assume the formula holds for all connected planar graphs with fewer than e edges. Consider a connected planar graph G with e edges.
Case 1 — G is a tree: Then e = v − 1 and f = 1 (trees have no cycles, so no bounded faces). Check: v + 1 = (v−1) + 2. ✓
Case 2 — G has a cycle: Find any cycle C. Remove one edge from C. Call the resulting graph G'. G' is still connected (the cycle gives an alternate path), has v vertices, e−1 edges, and f−1 faces (removing the edge merges two adjacent faces into one). By induction hypothesis applied to G': v + (f−1) = (e−1) + 2. Rearranging: v + f = e + 2. ✓ ∎
The Edge Bound for Planar Graphs
For any simple planar graph with v ≥ 3 vertices and e edges: e ≤ 3v − 6.
- Each face is bordered by at least 3 edges. Why? Each face is bounded by a closed walk, which must have length ≥ 3 in a simple graph (no multi-edges, no self-loops). So each face is incident to ≥ 3 edges.
- Count face-edge incidences from the face side: Each of the f faces contributes ≥ 3 incidences. Total ≥ 3f.
- Count face-edge incidences from the edge side: Each edge borders exactly 2 faces (one on each side — even boundary edges border the outer face). Total = 2e.
- Combine: 3f ≤ 2e, so f ≤ (2/3)e.
- Substitute into Euler: v + f = e + 2. Substituting f ≤ (2/3)e: v + (2/3)e ≥ e + 2. Rearranging: v − 2 ≥ e − (2/3)e = (1/3)e. Multiply by 3: 3v − 6 ≥ e. ∎
For a simple bipartite planar graph with v ≥ 3: e ≤ 2v − 4.
In a bipartite graph, all cycles have even length. So each face is bounded by a walk of length ≥ 4 (not just 3). Therefore: 4f ≤ 2e → f ≤ e/2. Substituting into Euler: v + e/2 ≥ e + 2 → v − 2 ≥ e/2 → e ≤ 2v − 4. ∎
K₅ Is Not Planar
The complete graph on 5 vertices cannot be drawn in the plane without edge crossings.
K₅ has v = 5 vertices and e = 5×4/2 = 10 edges.
If K₅ were planar, we'd need e ≤ 3v − 6 = 3(5) − 6 = 15 − 6 = 9.
But e = 10 > 9. Contradiction!
Therefore, K₅ is NOT planar. ∎
K₃,₃ Is Not Planar
The complete bipartite graph on 3+3 vertices cannot be drawn without crossings.
K₃,₃ has v = 6 vertices and e = 3×3 = 9 edges. It's bipartite (edges only between the two groups of 3).
If K₃,₃ were planar bipartite, we'd need e ≤ 2v − 4 = 2(6) − 4 = 8.
But e = 9 > 8. Contradiction! ∎
A graph is planar if and only if it contains no subgraph that is a subdivision of K₅ or K₃,₃. (A subdivision replaces edges with paths.) This completely characterizes planarity.
Graph Coloring
A proper k-coloring of a graph G = (V, E) assigns one of k colors to each vertex such that no two adjacent vertices share a color. The chromatic number χ(G) is the minimum number of colors needed.
Bipartite Graphs
χ(G) = 2. Two-colorable iff bipartite.
Complete Graph Kₙ
χ(Kₙ) = n. Every vertex must differ.
Cycle C₂ₙ (even)
χ = 2. Bipartite.
Cycle C₂ₙ₊₁ (odd)
χ = 3. Odd cycles need 3 colors.
For planar graphs, the famous Four Color Theorem says 4 colors suffice for any planar graph. We prove the 6-color and 5-color versions here.
The 6-Color Theorem
Every planar graph can be properly colored using at most 6 colors.
Key Observation: From e ≤ 3v−6, the average degree ≤ 2e/v ≤ 2(3v−6)/v = 6 − 12/v < 6. So the average degree is strictly less than 6, meaning there must exist a vertex with degree at most 5.
Base case: v ≤ 6. At most 6 vertices, use 6 distinct colors. ✓
Inductive step: Assume any planar graph with fewer than v vertices is 6-colorable. For G with v vertices:
- Find vertex u with deg(u) ≤ 5 (exists by average degree argument).
- Remove u from G. G − u has v−1 vertices and is planar.
- By IH, G − u is 6-colorable. Fix such a coloring.
- Restore u. u has at most 5 neighbors, which use at most 5 colors.
- At least one of the 6 colors is unused by u's neighbors. Assign that color to u. ∎
The 5-Color Theorem
Every planar graph can be properly colored using at most 5 colors.
In any proper coloring, consider all vertices colored with colors i or j. The connected components of this subgraph are called (i,j)-components. We can swap colors i and j within any single component and still have a valid proper coloring (swapping both colors preserves the "different from neighbors" property).
Again, by induction. The key case is handling the degree-5 vertex.
Find vertex u with deg(u) ≤ 5. Remove u, color G − u with 5 colors (by IH).
Restore u. If u has ≤ 4 neighbors, one color is unused → assign it to u. Done.
The hard case: u has exactly 5 neighbors v₁, v₂, v₃, v₄, v₅ (in cyclic order around u), all using distinct colors 1, 2, 3, 4, 5.
- Consider the (1,3)-component containing v₁. If it does NOT contain v₃, swap colors 1 and 3 in v₁'s component. Now v₁ gets color 3, and v₃ still has color 3... wait, we need: after swap, v₁ has color 3, but v₃ had color 3 and is in a DIFFERENT component, so v₃ is unchanged. Now no neighbor has color 1 → assign color 1 to u. Done!
- If the (1,3)-component DOES contain v₃: There is a path from v₁ to v₃ using only colors 1 and 3. This path, together with u, creates a closed curve that separates v₂ from v₄ in the plane (by planarity — the path from v₁ to v₃ around u blocks the path from v₂ to v₄).
- Therefore, the (2,4)-component containing v₂ cannot contain v₄ (they're separated by the (1,3)-path).
- Swap colors 2 and 4 in v₂'s (2,4)-component. Now v₂ gets color 4, v₄ still has color 4 (in a different component, unchanged). No neighbor has color 2 → assign color 2 to u. ∎
Planarity is crucial in step 2 — this argument fails for non-planar graphs.
The 4-Color Theorem
Every planar graph can be properly colored using at most 4 colors.
The proof of the 4-color theorem is one of the most famous in mathematics — and the most controversial, as it required checking ~1,900 cases by computer. It was the first major theorem proven with substantial computer assistance. The proof is not given in this course.
Practice Problems (DIS 2B)
"A connected planar simple graph has 5 more edges than vertices. How many faces?"
e = v + 5. Euler: v + f = e + 2 = (v+5) + 2 = v + 7. So f = 7.
Euler's formula v − e + f = 2 holds for connected graphs. For a planar graph with k connected components: v − e + f = k + 1.
Proof sketch: Each component satisfies v − e + f_component = 2. The outer (infinite) face is shared. Summing k components and correcting for the shared face: v − e + f = k + 1.
Prove: Any graph with maximum degree ≤ k is (k+1)-colorable.
Proof: By induction on v. Remove any vertex u (degree ≤ k). Color remaining by IH with k+1 colors. Restore u: has at most k neighbors using at most k colors. At least 1 of k+1 colors unused. Assign it. ∎