Lesson 2

Before stating the theorem, let us introduce one notion that will be used in the proof. Suppose a planar graph is already drawn on the plane. Its dual graph \(G^{*}\) is constructed as follows: put one new vertex in every face of \(G\); for the outer face, put it outside the drawing. For every edge \(e\) of \(G\), look at the faces on the two sides of \(e\) and draw a dual edge \(e^{*}\) between the corresponding dual vertices, crossing \(e\).

In the picture below, the black graph is \(G\), and the dashed red graph is \(G^{*}\).

Notice that the dual graph depends on the chosen planar drawing. We call edges of \(G\) primal edges, and edges of \(G^{*}\) dual edges. In general, dual graphs may have loops or parallel edges; this will not cause any difficulty for us.