Graph Theory 139

Theorem 104. The Euler characteristic of any finite nonempty connected planar nonempty

graph is 2.

v − e + f = 2

Proof. We prove the theorem by induction on the size of the graph or, more specifically,

on the number of edges appearing in the graph. The statement is true in the graph with one

vertex and no edges. Let us now imagine adding vertices and edges. If we add a single

new vertex and a new edge connecting it to a vertex we had before (in order that the graph

is connected), then we have increased v and e by 1, but we have not changed f ,sowe

still have v − e + f = 2. If we add an edge between two vertices we already have, then

this new edge cuts a previous face in two, and so we have increased e and f by 1, but we

have not changed v. And so the resulting graph still has v − e + f = 2. Since every finite

connected planar graph can be constructed by finitely many steps of these kinds, we see

that v − e + f = 2 in all of them.

The reader might enjoy exploring the idea of extending the Euler characteristic to three-

dimensional polyhedra, such as cubes, prisms, and other shapes. For example, a cube

has v = 8 vertices, e = 12 edges, and f = 6 faces, resulting in the Euler characteristic

v − e + f = 8 − 12 + 6 = 2. A triangular prism has six vertices, nine edges, and five faces,

leading to v − e + f = 6 − 9 + 5 = 2, once again. Similarly, a hexagonal prism has twelve

vertices, eighteen edges, and eight faces, leading to v−e+ f = 12−18+8 = 2. A pentagonal

prism has ten vertices, fifteen edges, and seven faces, leading to v −e + f = 10 −15 + 7 = 2,

once again. It works in all these cases and many more—amazing!

Mathematical Habits

Have favorite examples. For any mathematical idea, have a favorite example—a

favorite prime number, a favorite polynomial, a favorite discontinuous function, a

favorite graph. When learning a new idea, see how it plays out with your favorite

examples.