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. For a connected plane graph, delete non-bridge cycle edges one at a time. Each deletion merges two faces, reducing both e and f by one while preserving connectivity. The process ends in a tree with e=v−1 and f=1, proving the formula. For c components use v−e+f=1+c: an edge joining two components leaves f unchanged and reduces c by one.

From Euler's formula and the fact that every face boundary in a connected simple plane 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 connected simple bipartite plane graphs with $v \ge 3$ (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.

Planarity is a structural hypothesis, not a blanket guarantee of efficient exact optimization. Keep an existence theorem, an exact algorithm, and an approximation guarantee separate. This module proves edge-count obstructions and checks embeddings; it does not derive complexity claims for optimization problems on planar graphs.

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 (every simple planar graph with at least three vertices 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 is only aesthetic. Planar structure supports specialized algorithms and separator results under explicit hypotheses, but a physical network or circuit layout requires its own model; do not infer arbitrary runtime improvements from a drawing.

How To Use It​

  1. Don't trust one drawing. Always consider whether a redraw can remove crossings.
  2. Apply edge bounds first. For a simple graph with $v \ge 3$, $e > 3v - 6$ proves nonplanarity. If it is also bipartite, $e > 2v - 4$ does so. Check the hypotheses before using either bound.
  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. For a connected plane graph whose face boundary walks all have length at least $g>2$, count edge sides to obtain $2e \ge gf$ and $e \le \tfrac{g}{g-2}(v-2)$. Prove the boundary-length hypothesis, especially when bridges occur.
  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 to the workshop model​

Use this concept to justify or challenge one result in the workshop project. Specify the counted objects or graph semantics before interpreting any numerical output.

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 stated Four Color Theorem not justify four colors for an arbitrary graph? Give a nonplanar graph requiring more than four colors. Its full proof is outside this module.
  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​

Use the bounded reading guide to locate the topic in MCS or Rosen. These links open indexes. Check the actual heading in your edition, read one targeted explanation, then reconstruct the argument with the book closed.

Face boundaries count edge sides, including bridges twice​

In a plane embedding each edge has two sides; a bridge appears twice on the boundary of the same face. Face boundaries need not be simple cycles. For a connected simple plane graph with at least three vertices, their lengths support 3f≤2e, or 4f≤2e in the bipartite case. Combine this with Euler's formula to derive the respective necessary edge bounds.

Joining two components leaves the number of faces unchanged and reduces the number of components. Use v−e+f=1+c consistently. A subdivision obstruction can survive when added degree-two vertices make the numeric edge bounds uninformative. Transfer: P19–P20. Kuratowski's and Wagner's full characterizations are stated as deeper theorems here, not claimed as proofs developed in this module.

After your attempt use practice feedback and model contracts to check the argument.

For further reading on Euler’s formula and coloring hypotheses, see the MIT planarity and coloring notes.