# Chapter 38. Euler's Formula # Chapter 38. Euler's Formula Euler's formula is the basic counting law for connected plane graphs. It relates three quantities: the number of vertices, the number of edges, and the number of faces. If a connected planar graph is drawn without crossings, then $$ v - e + f = 2. $$ Here \(v\) is the number of vertices, \(e\) is the number of edges, and \(f\) is the number of faces, including the unbounded outer face. This formula holds for every finite connected plane graph. ## 38.1 Statement of the Formula Let \(G\) be a connected plane graph. Write $$ v = |V(G)|, \qquad e = |E(G)|, \qquad f = \text{number of faces of }G. $$ Then Euler's formula states that $$ v - e + f = 2. $$ The number $$ v - e + f $$ is called the Euler characteristic of the plane embedding. For connected plane graphs, its value is always \(2\). The drawing may change, the shapes of the faces may change, and the outer face may change, but the value remains the same. ## 38.2 First Examples A single vertex has $$ v = 1,\qquad e = 0,\qquad f = 1. $$ Hence $$ v - e + f = 1 - 0 + 1 = 2. $$ A triangle has $$ v = 3,\qquad e = 3,\qquad f = 2. $$ The two faces are the bounded triangular face and the unbounded outer face. Therefore $$ v - e + f = 3 - 3 + 2 = 2. $$ A square with one diagonal has $$ v = 4,\qquad e = 5,\qquad f = 3. $$ The diagonal divides the inside of the square into two triangular faces, and there is also the outer face. Thus $$ v - e + f = 4 - 5 + 3 = 2. $$ These examples show the pattern. Adding an edge may increase the number of faces. Adding a vertex may increase the number of edges. The alternating sum remains fixed. ## 38.3 Trees as the Base Case A tree with \(v\) vertices has $$ e = v - 1. $$ A tree has no cycle, so a plane drawing of a tree encloses no bounded face. Therefore it has only one face, the outer face: $$ f = 1. $$ Substituting into Euler's expression gives $$ v - e + f = v - (v-1) + 1 = 2. $$ Thus Euler's formula holds for every tree. This case is important because every connected graph contains a spanning tree. A connected plane graph can be reduced to a tree by deleting suitable edges from cycles. ## 38.4 Proof by Deleting Cycle Edges Let \(G\) be a connected plane graph. If \(G\) is a tree, the formula has already been proved. Suppose \(G\) is not a tree. Then \(G\) contains at least one cycle. Choose an edge \(a\) that lies on a cycle. Removing \(a\) does not disconnect the graph, because the rest of the cycle still gives a path between the endpoints of \(a\). Hence the new graph remains connected. What happens to \(v\), \(e\), and \(f\)? The number of vertices is unchanged: $$ v' = v. $$ The number of edges decreases by one: $$ e' = e - 1. $$ The removed edge separated two faces. After the edge is deleted, those two faces merge into one. Therefore $$ f' = f - 1. $$ Now compute: $$ v' - e' + f' = v - (e-1) + (f-1) = v - e + f. $$ Thus deleting a cycle edge preserves the value of \(v - e + f\). Repeat this process until no cycle remains. The resulting graph is a tree. Since the expression \(v - e + f\) did not change during the deletion process, and since it equals \(2\) for the final tree, it also equals \(2\) for the original graph. Therefore every connected plane graph satisfies $$ v - e + f = 2. $$ This is the standard edge-deletion proof of Euler's formula. ## 38.5 Why the Outer Face Counts The outer face must be counted. Without it, the formula would fail. For a triangle, the bounded region inside the triangle is one face. If only bounded faces were counted, then $$ v = 3,\qquad e = 3,\qquad f = 1, $$ and $$ v - e + f = 1. $$ Counting the outer face gives \(f = 2\), and the formula becomes $$ 3 - 3 + 2 = 2. $$ The outer face is not an exception. It is a genuine face of the embedding. It is unbounded, but it is still one of the connected regions left by the drawing. ## 38.6 Face Degrees The degree of a face is the number of edge appearances along its boundary. An edge may appear twice on the same face boundary, as happens with a bridge. For a connected plane graph, the sum of all face degrees is $$ 2e. $$ Each edge has two sides. In ordinary cases, those two sides border two different faces. If the edge is a bridge, both sides border the same face. In either case, the edge contributes two appearances to the total face-boundary count. Thus $$ \sum_{\text{faces } F} \deg(F) = 2e. $$ This identity is the face version of the handshaking lemma. ## 38.7 The Edge Bound for Simple Planar Graphs Euler's formula implies that simple planar graphs cannot have too many edges. Let \(G\) be a simple connected planar graph with \(v \geq 3\). Since \(G\) is simple, every face has degree at least \(3\). Therefore $$ 3f \leq 2e. $$ Euler's formula gives $$ f = 2 - v + e. $$ Substitute this into the inequality: $$ 3(2 - v + e) \leq 2e. $$ Expanding, $$ 6 - 3v + 3e \leq 2e. $$ Hence $$ e \leq 3v - 6. $$ So every simple planar graph with at least three vertices satisfies $$ e \leq 3v - 6. $$ This inequality is one of the most useful consequences of Euler's formula. It gives an immediate obstruction to planarity. ## 38.8 Application to \(K_5\) The complete graph \(K_5\) has $$ v = 5 $$ and $$ e = \binom{5}{2} = 10. $$ If \(K_5\) were planar, the edge bound would give $$ e \leq 3v - 6. $$ For \(v = 5\), $$ 3v - 6 = 15 - 6 = 9. $$ But \(K_5\) has \(10\) edges. Since $$ 10 > 9, $$ \(K_5\) is not planar. This proof avoids any attempt to draw all possible pictures of \(K_5\). The contradiction comes from counting alone. ## 38.9 Bipartite Planar Graphs A stronger edge bound holds for bipartite planar graphs. Let \(G\) be a simple connected bipartite planar graph with \(v \geq 3\). A bipartite graph has no odd cycle. In particular, it has no triangle. Therefore every face has degree at least \(4\). Thus $$ 4f \leq 2e. $$ Equivalently, $$ 2f \leq e. $$ Using Euler's formula, $$ f = 2 - v + e. $$ Substitute: $$ 2(2 - v + e) \leq e. $$ Then $$ 4 - 2v + 2e \leq e. $$ Therefore $$ e \leq 2v - 4. $$ So every simple connected bipartite planar graph with at least three vertices satisfies $$ e \leq 2v - 4. $$ ## 38.10 Application to \(K_{3,3}\) The complete bipartite graph \(K_{3,3}\) has two parts of size \(3\). It has $$ v = 6 $$ and $$ e = 3 \cdot 3 = 9. $$ If \(K_{3,3}\) were planar, the bipartite planar edge bound would give $$ e \leq 2v - 4. $$ For \(v = 6\), $$ 2v - 4 = 12 - 4 = 8. $$ But \(K_{3,3}\) has \(9\) edges. Since $$ 9 > 8, $$ \(K_{3,3}\) is not planar. Together, \(K_5\) and \(K_{3,3}\) are the two classical minimal obstructions that appear in Kuratowski's theorem. ## 38.11 Disconnected Plane Graphs Euler's formula in the form $$ v - e + f = 2 $$ assumes that the graph is connected. If a plane graph has \(c\) connected components, then the formula becomes $$ v - e + f = c + 1. $$ For example, two disjoint triangles have $$ v = 6,\qquad e = 6. $$ The drawing has three faces: the inside of the first triangle, the inside of the second triangle, and the common outer face. Thus $$ f = 3. $$ Hence $$ v - e + f = 6 - 6 + 3 = 3. $$ Since \(c = 2\), $$ c + 1 = 3. $$ The formula agrees. ## 38.12 Euler's Formula and Polyhedra Euler's formula first appears naturally in the study of polyhedra. A convex polyhedron has vertices, edges, and faces, and these satisfy $$ V - E + F = 2. $$ A convex polyhedron can be projected onto the plane by choosing one face as the outer face. The resulting drawing is a connected plane graph. This explains why the same formula governs both convex polyhedra and connected planar graphs. For a cube, $$ V = 8,\qquad E = 12,\qquad F = 6. $$ Then $$ V - E + F = 8 - 12 + 6 = 2. $$ For a tetrahedron, $$ V = 4,\qquad E = 6,\qquad F = 4. $$ Then $$ V - E + F = 4 - 6 + 4 = 2. $$ The graph-theoretic version and the polyhedral version are expressions of the same topological invariant. ## 38.13 Limits of the Formula Euler's formula gives necessary conditions for planarity, but it does not give sufficient conditions. If a graph violates $$ e \leq 3v - 6, $$ then it is nonplanar. But if a graph satisfies this inequality, it may still be nonplanar. For example, \(K_{3,3}\) has $$ v = 6,\qquad e = 9. $$ The general planar bound gives $$ 3v - 6 = 12. $$ Since \(9 \leq 12\), the general bound alone does not rule out planarity. The bipartite bound is needed. Even that is still not a complete planarity test. Complete characterizations require deeper theorems, such as Kuratowski's theorem or Wagner's theorem. ## 38.14 Summary Euler's formula states that every connected plane graph satisfies $$ v - e + f = 2. $$ It can be proved by reducing a connected plane graph to a tree through deletion of cycle edges. Each such deletion lowers both the edge count and the face count by one, leaving \(v - e + f\) unchanged. The formula has several important consequences: | Result | Formula | |---|---| | Connected plane graph | \(v - e + f = 2\) | | Disconnected plane graph with \(c\) components | \(v - e + f = c + 1\) | | Simple planar graph, \(v \geq 3\) | \(e \leq 3v - 6\) | | Simple bipartite planar graph, \(v \geq 3\) | \(e \leq 2v - 4\) | | Sum of face degrees | \(\sum \deg(F) = 2e\) | Euler's formula is a counting theorem, but its force is structural. It shows that planar graphs are sparse, explains the nonplanarity of \(K_5\) and \(K_{3,3}\), and connects graph theory with the topology of surfaces.