Lesson 2

A face of a polyhedron is a natural concept we know from childhood. It can also be defined for planar graphs: these are the regions into which a planar graph divides the plane. One of them is always infinite and is called the outer face. For a plane graph \(G\), we denote its set of faces by \(F(G)\).

The planar graph shown below has five faces. They are bounded by the following five cycles: \((A, H, G)\), \((A, B, E, F, G)\), \((B, C, E)\), \((F, E, G)\), and \((G, H, A, B, C, E, F)\). As we see, many edges belong to the boundaries of two faces, but there are also edges \(\{B,D\}\) and \(\{E,I\}\) that belong to a single face boundary (they are called bridges). Also, each face is bounded by at least three edges. This is always the case for connected graphs with at least three edges.

It turns out that if a graph \(G\) is planar, then in any of its embeddings the number of faces is always the same. This is a direct consequence of Euler's formula, which we prove below.