Skip to main content

Planarity, Euler's Formula, and Forbidden Structure

What This Concept Is​

A graph is planar if it can be drawn in the plane with no crossing edges. Planarity is not about whether a particular sketch has crossings -- it is about whether some crossing-free drawing exists. A planar graph together with a chosen crossing-free drawing is called a plane graph, and the drawing partitions the plane into connected regions called faces (including one unbounded outer face).

Euler's formula for a connected plane graph states:

$$v - e + f = 2,$$

where $v$ is the number of vertices, $e$ the number of edges, and $f$ the number of faces. The formula is proved by induction on $e$: for trees, $e = v - 1$ and $f = 1$, so $v - (v-1) + 1 = 2$. Adding an edge either creates a new face (if it closes a cycle) or connects two components (decreasing $f$ implicitly by merging); in both cases $v - e + f$ is preserved.

From Euler's formula and the fact that every face in a simple graph (with $v \ge 3$) has boundary of length at least $3$, we derive the edge bound:

$$e \le 3v - 6.$$

This single inequality blocks many graphs from being planar. For bipartite planar graphs (no triangles), every face has boundary length at least $4$, and the bound tightens to $e \le 2v - 4$.

Forbidden minors. Two graphs play a special role:

  • $K_5$: complete graph on $5$ vertices, with $v = 5, e = 10$, violating $10 \le 3(5) - 6 = 9$.
  • $K_{3,3}$: complete bipartite graph with parts of size $3$, with $v = 6, e = 9$, violating the bipartite bound $9 \le 2(6) - 4 = 8$.

Kuratowski's theorem (1930). A graph is planar $\iff$ it does not contain a subdivision of $K_5$ or $K_{3,3}$. Wagner's theorem (1937) gives the cleaner minor-closed form: $G$ is planar $\iff$ $G$ contains neither $K_5$ nor $K_{3,3}$ as a minor (a graph obtained by deleting vertices, deleting edges, and contracting edges).

These two theorems transform planarity from a geometric condition into a purely combinatorial one -- a pivotal result of 20th-century graph theory.

Why It Matters Here​

Planarity gives a striking example of how a geometric/topological property yields powerful combinatorial constraints. You learn to combine Euler's formula (global), edge bounds (averaged local), and forbidden-substructure reasoning (existence) into coherent proofs.

Planar graphs support algorithms far faster than their general counterparts: planarity testing is $O(n)$ (Hopcroft-Tarjan, 1974); many NP-hard problems (max independent set, 3-coloring) have polynomial-time algorithms on planar graphs (Baker's framework, 1983). This sets up your later intuition that recognizing which graph class you are in can reduce an NP-hard task to a tractable one.

Planarity is also the canonical case for the Four Color Theorem and for the Robertson-Seymour minor theorem (one of the deepest results in modern graph theory, asserting that every infinite family of graphs closed under minors has a finite forbidden-minor characterization).

Concrete Examples​

Example 1: $K_5$ is nonplanar. $K_5$ has $v = 5$, $e = \binom{5}{2} = 10$. The simple-graph bound gives $e \le 3v - 6 = 9$. Since $10 > 9$, $K_5$ cannot be planar. No trial drawing is needed -- the edge count alone settles it.

Example 2: $K_{3,3}$ is nonplanar. $K_{3,3}$ has $v = 6$, $e = 9$. The simple-graph bound $e \le 3v - 6 = 12$ does not rule it out -- so a refinement is needed. Observe $K_{3,3}$ is bipartite, hence triangle-free, so every face has boundary of length at least $4$. Counting face-edge incidences: $2e \ge 4f \Rightarrow f \le e/2 = 4.5$, so $f \le 4$. Euler's formula then gives $v - e + f = 6 - 9 + f = f - 3 = 2$, forcing $f = 5$. Contradiction: $f \le 4$ but $f = 5$. So $K_{3,3}$ is nonplanar.

Example 3: a "big" graph that might still be planar. Consider a simple graph with $v = 10$ and $e = 23$. The edge bound says $e \le 3(10) - 6 = 24$. So the bound does not rule out planarity. You must actually try to draw it or invoke Kuratowski/Wagner. The bound is necessary but not sufficient -- this is a critical subtlety.

Example 4: using Euler for cube graph. $Q_3$ (cube graph) has $v = 8, e = 12$, and (when drawn in the plane) $f = 6$: $8 - 12 + 6 = 2$. ✓ Every face of $Q_3$ is a square, hence bipartite bound is tight: $e = 2v - 4 = 12$. ✓

Common Confusion / Misconceptions​

  • "My picture has crossings, so the graph is nonplanar." Wrong. Planarity is a property of the abstract graph, not of one drawing. You must ask whether some crossing-free drawing exists. Always try to redraw before concluding.
  • "Euler's formula applies to any graph." Euler's formula as stated ($v - e + f = 2$) is for connected plane graphs. For a plane graph with $c$ connected components, it becomes $v - e + f = 1 + c$.
  • "The edge bound $e \le 3v - 6$ proves planarity." No. It is necessary (any planar graph satisfies it) but not sufficient. $K_{3,3}$ has $e = 9 \le 3(6) - 6 = 12$ yet is nonplanar. To prove planarity, you need Kuratowski / Wagner or an explicit embedding.
  • "Minor" = "subgraph." Different: a subgraph drops vertices/edges, while a minor also allows edge contractions. Wagner's theorem uses minors; Kuratowski's uses subdivisions. They are equivalent characterizations but operate on different operations.
  • "Planarity helps only aesthetically." No. It gives genuine algorithmic speedups: $O(n)$ testing, $O(n)$ many-algorithms, and separator theorems (Lipton-Tarjan: any planar graph has a $\sqrt{n}$-size separator).

How To Use It​

  1. Don't trust one drawing. Always consider whether a redraw can remove crossings.
  2. Apply edge bounds first. If $e > 3v - 6$, the graph is nonplanar immediately. If bipartite and $e > 2v - 4$, same story.
  3. Know your obstructions. Look for $K_5$ or $K_{3,3}$ as subdivisions/minors. If found, nonplanar.
  4. Use face counting for nonstandard bounds. Larger face girth gives tighter bounds: if smallest face has $g$ edges, then $2e \ge gf$, leading to $e \le \tfrac{g}{g-2}(v-2)$.
  5. Try constructive embeddings. Place vertices on a circle or use a planarity-testing algorithm (e.g., Boyer-Myrvold, Hopcroft-Tarjan).
  6. Exploit the Four Color Theorem. For any planar graph, $\chi \le 4$ without further argument.
  7. If the graph is almost planar, consider genus (minimum genus surface on which it embeds) -- relevant for $3$D routing and VLSI.

Transfer / Where This Shows Up Later​

  • Semester 2 algorithms: $O(n)$ planarity testing; Baker's framework for PTAS on planar graphs; planar separator theorem for divide-and-conquer.
  • Semester 3 data structures: spatial index structures (R-trees, kd-trees) leverage planar subdivisions; polygon decomposition in computational geometry uses planar duals.
  • Semester 4 databases: geographic information systems (GIS) store planar subdivisions explicitly; route-planning graphs on road networks are nearly planar (efficient contraction-hierarchy algorithms exploit this).
  • Semester 5 OS: graphical user interfaces use planar Voronoi / Delaunay structures for hit-testing; window management involves planar layout constraints.
  • Semester 6 distributed systems: network topologies that are planar (torus, mesh) admit routing algorithms with bounded stretch. VLSI placement and PCB routing are planar or near-planar drawing problems.
  • Semester 7 architecture: service-dependency diagrams are often planar (or require genus $1$); visualizing architecture on a whiteboard favors planar or near-planar designs for cognitive clarity.
  • Compilers and circuits: standard cell layout in chip design uses planar/near-planar routing; crossing-minimization is a core objective.

Check Yourself​

  1. Why is planarity a property of the graph, not a particular drawing?
  2. Derive $e \le 3v - 6$ for simple planar graphs with $v \ge 3$.
  3. Why does the bipartite bound $e \le 2v - 4$ improve on $e \le 3v - 6$? What changes in the face-length argument?
  4. What is the difference between a subgraph, a subdivision, and a minor? Which appears in Kuratowski's theorem?
  5. Why does the Four Color Theorem apply only to planar graphs? Where does the proof use planarity?
  6. For a connected plane graph with $v = 12, e = 24$: how many faces?

Mini Drill or Application​

Use Euler-style reasoning to decide planarity:

  1. A simple graph with $v = 8$, $e = 19$. (Compare to $3v - 6 = 18$. Conclusion?)
  2. $K_5$. (Apply edge bound directly.)
  3. $K_{3,3}$. (Apply bipartite bound.)
  4. A simple bipartite graph with $v = 10$, $e = 17$. (Compare to $2v - 4 = 16$. Conclusion?)
  5. The Petersen graph ($v = 10$, $e = 15$, girth $5$). Use the girth-$g$ bound $e \le \tfrac{g}{g-2}(v-2)$ to test planarity.

For each, decide if the bound alone settles the case; if not, outline the further argument needed.

Read This Only If Stuck​