Induct on $m$. Base: $m=0$ gives a single vertex, so $n=1$, $f=1$ (outer face), and $1-0+1=2$ ✓.

Inductive step: Given graph $G$ with $m > 0$, remove an edge $e$.

Case 1: $e$ is a bridge (removing disconnects graph). Then $G-e$ has two components. For each component with $(n_i, m_i, f_i)$, by induction $n_i - m_i + f_i = 2$. But both components share the outer face, so: $n - (m-1) + f = (n_1 + n_2) - (m_1 + m_2) + (f_1 + f_2 - 1) = 4 - 1 = 3$ Wait, this needs adjustment. Actually, the faces merge: $f(G-e) = f(G) -1$ if $e$ is not a bridge.

Case 2: $e$ is not a bridge. Then $G-e$ is connected with $(n, m-1, f-1)$ faces (two faces merge). By induction: $n-(m-1)+(f-1)=2$, so $n-m+f=2$ ✓.

For dual graph $G^*$, we have $n(G^*) = f(G)$, $m(G^*) = m(G)$, $f(G^*) = n(G)$. If the formula holds for $G$, then: $n(G) - m(G) + f(G) = 2$ $f(G^*) - m(G^*) + n(G^*) = 2$ This is Euler's formula for $G^*$. Since $(G^*)^* = G$, the formula is self-dual.

Add edges until the graph is maximal planar (every face is a triangle). This preserves $n-m+f$. For a triangulated plane graph with $n$ vertices, each face is a triangle and $3f = 2m$ (each edge borders 2 faces, each face has 3 edges). The outer face also has 3 edges, so $f = 2m/3$ for interior faces plus 1 for exterior. Algebra gives $m = 3n - 6$ and $f = 2n - 4$. Then: $n - m + f = n - (3n-6) + (2n-4) = n - 3n + 6 + 2n - 4 = 2$