[proofplan] We induct on the number of edges $|E(G)|$. The base case is a tree, where the formula holds by a direct count: a tree with $n$ vertices has $n - 1$ edges and exactly $1$ face (the unbounded region). The inductive step deletes an edge $e$ that lies on some cycle — such an edge exists whenever $G$ is not a tree — and uses the key planar fact that removing a cycle edge merges the two faces bordering it into one, leaving a connected plane graph $G - e$ with one fewer edge and one fewer face. Applying the inductive hypothesis to $G - e$ and rearranging yields Euler's formula for $G$. [/proofplan] [step:Set up induction on the number of edges] Let $G$ be a connected plane graph. Write $n := |V(G)|$, $m := |E(G)|$, and let $F$ denote the number of faces of the planar embedding (i.e., the connected components of $\mathbb{R}^2 \setminus G$, including the unbounded outer face). We prove \begin{align*} n - m + F = 2 \end{align*} by induction on $m \ge 0$, with $n$ and $F$ free to vary. [guided] Two comments before we begin. First, note that Euler's formula is a statement about a **plane graph** — a graph together with a specific planar embedding — not merely a planar graph (a graph that admits some planar embedding). The quantity $F$ depends on the embedding; the theorem asserts that the alternating sum is the same for any embedding, but $F$ itself is defined by the drawing in front of us. Second, the choice to induct on $m$ rather than $n$ or $F$ is motivated by the inductive step: we will remove a single edge at a time, which decrements $m$ by exactly $1$ and leaves $n$ unchanged; whether $F$ drops by $1$ or the graph disconnects depends on whether the removed edge lies on a cycle. The base case is the minimum value of $m$ for a connected graph on $n$ vertices, which is $m = n - 1$ — a tree. [/guided] [/step] [step:Establish the base case: $G$ is a tree] Suppose $G$ contains no cycle. Then $G$ is a connected acyclic graph, i.e., a **tree**. A tree on $n$ vertices has exactly $n - 1$ edges (proved by induction on $n$: a leaf can always be removed, decrementing both vertex and edge counts by $1$, reducing to the single-vertex case $n = 1$, $m = 0$). A plane tree has exactly $F = 1$ face. To see this: since $G$ is acyclic, $\mathbb{R}^2 \setminus G$ is connected — the complement of a tree (viewed as a $1$-dimensional subset of the plane) is path-connected, because any two points in the complement can be joined by a path that locally detours around any edge of the tree without needing to cross it (there is no cycle to obstruct). Thus there is a unique face. Substituting: \begin{align*} n - m + F = n - (n - 1) + 1 = 2. \end{align*} This establishes the base case for every tree, including the minimum case $m = 0$, $n = 1$, $F = 1$. [guided] Let us unpack the claim that the complement of a plane tree has exactly one face. A **face** of a plane graph is a connected component of $\mathbb{R}^2 \setminus G$ — where $G$ is identified with its drawing: the union of the vertex points and the Jordan arcs representing its edges. A cycle in the plane is a Jordan curve, and by the Jordan curve theorem its complement has exactly two components. Without any cycle, no such obstruction exists, and the complement remains connected. A direct way to see this for trees: we can shrink a plane tree continuously to a single point via a sequence of leaf-collapses (each leaf and its incident edge can be retracted onto the rest of the tree). Each collapse does not change the number of faces (since collapsing a leaf does not cut any region in two). A single point has exactly one complementary face, the punctured plane. Hence every plane tree has $F = 1$. The edge count $m = n - 1$ for a tree is the "minimum spanning connectivity": any connected graph on $n$ vertices has at least $n - 1$ edges, with equality iff it is a tree. [/guided] [/step] [step:Set up the inductive step: pick an edge on a cycle] Suppose now that $G$ contains a cycle and that Euler's formula holds for every connected plane graph with strictly fewer edges. Since $G$ is not a tree, it contains at least one cycle; let $e = \{u, v\}$ be an edge lying on some cycle $C$ of $G$. Consider the plane graph $G - e$ obtained by deleting the edge $e$ (keeping all vertices and all other edges, with the same embedding of those edges). We claim: [claim:$G - e$ is connected] The edge $e$ lies on a cycle $C = u = w_0, w_1, \ldots, w_{k-1}, w_k = u$ with $\{u, v\} = \{w_0, w_1\}$, so $v = w_1$. Within $C$, the path $v = w_1, w_2, \ldots, w_k = u$ connects $v$ to $u$ and does not use the edge $e$. Hence in $G - e$, the vertices $u$ and $v$ remain connected by this detour. Any other pair of vertices $x, y \in V(G)$ was connected in $G$ by some path; if that path used $e$, we splice in the detour $w_1 \to w_2 \to \ldots \to w_k$ (or its reverse) in place of the traversal of $e$, producing a walk from $x$ to $y$ in $G - e$. Therefore $G - e$ is connected. [/claim] [/step] [step:Show that deleting a cycle edge decreases the face count by exactly one] [claim:$G - e$ has exactly $F - 1$ faces] Let $F' := F(G - e)$ denote the number of faces of $G - e$. We show $F' = F - 1$. The cycle $C$ containing $e$ is a Jordan curve in the plane. By the Jordan curve theorem, $\mathbb{R}^2 \setminus C$ has two connected components: the bounded interior $\operatorname{Int}(C)$ and the unbounded exterior $\operatorname{Ext}(C)$. The edge $e$ (an open Jordan arc joining $u$ to $v$) therefore lies on the boundary between a face $f_1 \subseteq \operatorname{Int}(C)$ and a face $f_2 \subseteq \operatorname{Ext}(C)$, and $f_1 \ne f_2$: any path from a point of $f_1$ to a point of $f_2$ must cross $C$, in particular must cross the edge $e$ if it stays close to $e$. When $e$ is deleted, the open arc representing $e$ is removed from $G$, so points just above and just below $e$ become connected through the gap: the faces $f_1$ and $f_2$ merge into a single face $f_1 \cup e \cup f_2$ of $G - e$. No other face is affected, because removing the single arc $e$ cannot disconnect any region that did not previously touch $e$, and cannot connect any two faces not separated by $e$. Thus the $F$ faces of $G$ collapse to the $F - 1$ faces of $G - e$: one merged face and the $F - 2$ faces untouched by $e$. [/claim] [guided] The crux of Euler's formula is this one fact: deleting a cycle edge of a plane graph decreases the face count by exactly $1$. Contrast this with deleting a bridge (an edge not on any cycle): in that case $G - e$ would disconnect, and the face count would not drop — this is exactly why we must pick $e$ on a cycle. The argument above is the standard Jordan-curve argument. A cycle $C$ is drawn in the plane as a simple closed curve, which by the Jordan curve theorem separates the plane into exactly two regions. Any edge $e$ on the cycle bounds two distinct faces of $G$ — one on each side. Deleting $e$ unites the two faces that touched it, while leaving the rest of the embedding alone. A subtle point: the theorem states "the two faces sharing $e$ merge". Why does $e$ have two distinct faces on its sides, rather than one face on both sides? Precisely because $e$ lies on a cycle, and the cycle separates the plane. If $e$ were a bridge, it would have the **same** face on both sides (the bridge does not separate), and removing $e$ would disconnect $G$ without changing $F$ — a different regime. [/guided] [/step] [step:Apply the inductive hypothesis to $G - e$] By the two claims, $G - e$ is a connected plane graph with \begin{align*} |V(G - e)| &= n, \\ |E(G - e)| &= m - 1, \\ F(G - e) &= F - 1. \end{align*} Since $|E(G - e)| = m - 1 < m$, the inductive hypothesis applies: \begin{align*} n - (m - 1) + (F - 1) = 2. \end{align*} Simplifying: \begin{align*} n - m + 1 + F - 1 = n - m + F = 2. \end{align*} This is Euler's formula for $G$. [guided] The inductive step is purely arithmetic once the two claims are in hand: the vertex count is untouched, the edge count drops by $1$, and the face count drops by $1$. These two drops cancel in the alternating sum $n - m + F$, so the invariant is preserved. This is the structural reason the alternating sum is an invariant: every local move on a plane graph (adding or deleting a cycle edge) changes $m$ and $F$ by the same amount, leaving $n - m + F$ fixed. The base case — a tree — pins the invariant at the value $2$. [/guided] [/step] [step:Combine the base case and inductive step to conclude] By strong induction on $m$: for every connected plane graph $G$, either $G$ is a tree (the base case handled in the earlier step), or $G$ contains a cycle and Euler's formula for $G$ follows from Euler's formula for $G - e$ via the inductive step. In either case, \begin{align*} |V(G)| - |E(G)| + F = 2. \end{align*} [/step]