Planar graphs

This single identity is the source of almost every other fact about planar graphs, including the edge-count bound and the non-planarity of $K_5$ and $K_{3,3}$, and it is proved by a short, fully elementary induction.

Base case. If $E$ $= 0$ and the graph is connected, it must consist of a single vertex ($V=1$), and there is exactly one face, the entire unbounded plane ($F=1$). Then $1 - 0 + 1 = 2$ holds.

Inductive step, case 1: an edge lying on a cycle. Suppose the formula holds for every connected plane graph with fewer than $E$ edges, and let the graph have $E$ $\ge 1$ edges. If some edge $e$ lies on a cycle, then removing $e$ keeps the graph connected (the rest of the cycle still connects its two endpoints). Removing $e$ merges the two faces on its two sides into a single face, so the smaller graph has $V$ vertices, $E - 1$ edges and $F - 1$ faces. By the inductive hypothesis, $V - (E-1) + (F-1) = 2$, which simplifies to $V - E + F = 2$.

Inductive step, case 2: no edge lies on a cycle. Then every edge is a bridge, meaning the graph has no cycles at all, i.e. it is a tree. A tree drawn in the plane has exactly one face ($F = 1$, the single unbounded region, since there is no cycle to enclose any bounded region), and a standard fact about trees is that a tree on $V$ vertices has exactly $E = V - 1$ edges. Substituting, $V - E + F = V - (V - 1) + 1 = 2$.

Conclusion. Every case reduces to the formula holding, or reduces (via removing one edge) to a smaller graph where it holds by induction, so $V - E + F = 2$ for every connected plane graph.

This gives a complete, checkable characterization of planarity purely in terms of two small forbidden patterns, turning an existential question (can we find some crossing-free drawing?) into a search for one of two specific obstructions.

Why $K_5$ and $K_{3,3}$ themselves are not planar. $K_5$ has $V=5$ vertices and $E=10$ edges, but the edge bound $E \le 3V - 6$ requires $10 \le 3(5)-6=9$, a contradiction, so $K_5$ is not planar. $K_{3,3}$ is bipartite with $V=6$ vertices and $E=9$ edges; a planar bipartite graph must satisfy the tighter bound $E \le 2V - 4$, requiring $9 \le 2(6)-4=8$, again a contradiction, so $K_{3,3}$ is not planar either.

Subdivisions preserve non-planarity (the easy direction). If a graph $H$ is a subdivision of a graph $G$ (each edge of $G$ replaced by an internally disjoint path), and $G$ is not planar, then $H$ cannot be planar either: any crossing-free drawing of $H$ could be turned into one of $G$ simply by erasing the internal degree-2 vertices on each path and straightening it back into a single edge, which does not introduce any new crossings. So any graph containing a subdivision of $K_5$ or $K_{3,3}$ as a subgraph automatically fails to be planar, which proves the only-if direction of the theorem.

The converse (hard direction), sketch. That every non-planar graph must contain such a subdivision is the deep part, proved independently by Kuratowski in 1930 and, in an equivalent minor-based form, by Wagner in 1937. The argument proceeds by taking a hypothetical minimal non-planar graph containing no subdivision of $K_5$ or $K_{3,3}$ and deriving a contradiction: using Menger's theorem on connectivity, one first reduces to the case where the graph is 3-connected (graphs with a small vertex cut can be split along that cut into smaller planar-or-smaller pieces and reassembled), and then shows directly that every 3-connected non-planar graph of minimum size already contains one of the two forbidden subdivisions. This structural reduction via connectivity is where the real difficulty of the theorem lies.

Conclusion. Combining both directions, a graph is planar exactly when it avoids both forbidden subdivisions, giving the full characterization.