SECTION 2.2 Elementary Graph Theory 139
Euler’s formula and consequences
Once a planar graph has been drawn in the plane, it not only de-
termines vertices andedges, it also determinesfaces. These are the
2-dimensional regions (exactly one of which is unbounded) which are
bounded by the edges of the graph. The plane, together with a graph
faithfully drawn in it is called aplanar map. Thus, a planar map has
the vertices and edges of the “embedded” graphG, it also has faces.
Example 2. We look at the cube
graph drawn in the plane. Notice
that there are 6 naturally defined
regions, orfaces.
Example 3. Here is a more irreg-
ular planar graph with the faces in-
dicated. Also, we have computed
#vertices−#edges + #faces = 2;this is a fundamental result.
If we compute #vertices−#edges + #faces for the planar map in
Example 2 above, we also get 2. There must be something going on
here! We start by defining theEuler characteristicof the planar map
Mby setting
χ(M) = #vertices−#edges + #faces.The surprising fact is that the number always produced by the above