12.3: Euler’s Formula

Last updated
Save as PDF

Page ID: 48379

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

The value of the recursive definition is that it provides a powerful technique for proving properties of planar graphs, namely, structural induction. For example, we will now use Definition 12.2.2 and structural induction to establish one of the most basic properties of a connected planar graph, namely, that the number of vertices and edges completely determines the number of faces in every possible planar embedding of the graph.

Theorem \(\PageIndex{1}\)

(Euler’s Formula). If a connected graph has a planar embedding, then

\[\nonumber v - e + f = 2\]

where \(v\) is the number of vertices, \(e\) is the number of edges, and \(f\) is the number of faces.

For example, in Figure 12.5, \(v = 4, e = 6,\) and \(f = 4\). Sure enough, \(4 - 6 + 4 = 2\), as Euler’s Formula claims.

Proof

The proof is by structural induction on the definition of planar embeddings. Let \(P(\epsilon)\) be the proposition that \(v - e + f = 2\) for an embedding, \(\epsilon\).

Base case (\(\epsilon\) is the one-vertex planar embedding): By definition, \(v = 1, e = 0,\) and \(f = 1\), and \(1 - 0 + 1 = 2\), so \(P(\epsilon)\) indeed holds.

Constructor case (split a face): Suppose \(G\) is a connected graph with a planar embedding, and suppose \(a\) and \(b\) are distinct, nonadjacent vertices of \(G\) that appear on some discrete face, \(\gamma = a \ldots b \cdots a\), of the planar embedding.

Then the graph obtained by adding the edge \(\langle a - b \rangle\) to the edges of \(G\) has a planar embedding with one more face and one more edge than \(G\). So the quantity \(v - e + f\) will remain the same for both graphs, and since by structural induction this quantity is 2 for \(G\)’s embedding, it’s also 2 for the embedding of \(G\) with the added edge. So \(P\) holds for the constructed embedding.

Constructor case (add bridge): Suppose \(G\) and \(H\) are connected graphs with planar embeddings and disjoint sets of vertices. Then connecting these two graphs with a bridge merges the two bridged faces into a single face, and leaves all other faces unchanged. So the bridge operation yields a planar embedding of a connected graph with \(v_G + v_H\) vertices, \(e_G + e_H + 1\) edges, and \(f_G + f_H - 1\) faces. Since

\[\nonumber \begin{aligned} (v_G &+ v_H) - (e_G + e_H + 1) + (f_G + f_H - 1) \\ &= (v_G - e_G + f_G) + (v_H - e_H + f_H) - 2 \\ &= (2) + (2) - 2 & \text{(by structural induction hypothesis)}\\ &=2, \end{aligned}\]

\(v - e + f\) remains equal to 2 for the constructed embedding. That is, \(P(\epsilon)\) also holds in this case. This completes the proof of the constructor cases, and the theorem follows by structural induction. \(\quad \blacksquare\)