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

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

Then Euler’s formula states that

The number

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

Hence

A triangle has

The two faces are the bounded triangular face and the unbounded outer face. Therefore

A square with one diagonal has

The diagonal divides the inside of the square into two triangular faces, and there is also the outer face. Thus

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

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:

Substituting into Euler’s expression gives

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:

The number of edges decreases by one:

The removed edge separated two faces. After the edge is deleted, those two faces merge into one. Therefore

Now compute:

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

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

and

Counting the outer face gives $f = 2$, and the formula becomes

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

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

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

Euler’s formula gives

Substitute this into the inequality:

Expanding,

Hence

So every simple planar graph with at least three vertices satisfies

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

and

If $K_5$ were planar, the edge bound would give

For $v = 5$,

But $K_5$ has $10$ edges. Since

$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

Equivalently,

Using Euler’s formula,

Substitute:

Then

Therefore

So every simple connected bipartite planar graph with at least three vertices satisfies

38.10 Application to $K_{3,3}$

The complete bipartite graph $K_{3,3}$ has two parts of size $3$. It has

and

If $K_{3,3}$ were planar, the bipartite planar edge bound would give

For $v = 6$,

But $K_{3,3}$ has $9$ edges. Since

$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

assumes that the graph is connected.

If a plane graph has $c$ connected components, then the formula becomes

For example, two disjoint triangles have

The drawing has three faces: the inside of the first triangle, the inside of the second triangle, and the common outer face. Thus

Hence

Since $c = 2$,

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

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,

Then

For a tetrahedron,

Then

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

then it is nonplanar. But if a graph satisfies this inequality, it may still be nonplanar.

For example, $K_{3,3}$ has

The general planar bound gives

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

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:

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.