140 CHAPTER 2 Discrete Mathematics
is 2:
Theorem. (Euler’s Formula)If M be a connected planar map, then
χ(M) = 2.
Proof. Let T be a maximal spanning tree inside G; the existence
of T was proved in the footnote on page 125. Note that since T has
no cycles, there can only be one face: f = 1. Next, we know by the
theorem on page 125 thatv=e+ 1. Therefore, we know already that
χ(T) =v−e+f = 1 + 1 = 2. Next, we start adding the edges ofG
to the treeT, noting that each additional edge divides an existing face
in two. Therefore the expressionv−e+f doesn’t change aseandf
have both increased by 1, proving the result.^38
Corollary. For the simple planar map M, we have e≤ 3 v− 6.
Proof. We may assume thatMhas at least three edges, for otherwise
the underlying graph is a tree, where the result is easy. This easily
implies that each face—including the infinite face—will be bounded by
at least three edges. Next, notice that an edge will bound either a
single face or two faces. If the edge ebounds a single face, then the
largest connected subgraph containingeand whose edges also bound a
single face is—after a moment’s thought—seen to be a tree. Removing
all edges of this tree and all vertices sitting on edges bounding a single
face will result in removing the same number of vertices as edges. On
the mapM′which remains every edge bounds exactly two faces. Also,
the number f of faces of M′ is the same as the number of faces of
the original map M. Letv′,e′be the number of vertices and edges,
respectively, ofM′. Since every face ofM′is bounded by at least three
edges, and since every edge bounds exactly two faces of M′ we infer
that 3f ≤ 2 e′. Therefore,
2 = v′−e′+f ≤v′−e′+ 2e′/3 =v′−e′/ 3 ,(^38) In the most general setting, theEuler characteristicof a graph is a function of where it’s
faithfully drawn. For example, it turns out that the Euler characteristic of a graph faithfully drawn
on the surface of a doughnut (a “torus”) is always 0. See also the footnote on page 196.