Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / R

Choose a spanning tree of the connected plane graph. A tree with $n$ vertices has $n-1$ edges and one face of a plane graph, so $n-(n-1)+1=2$. Add the remaining drawn edges one at a time. Each joins two existing vertices and closes a cycle in a graph; its interior lies in one current face of a plane graph, splitting that face of a plane graph into two by the Jordan curve theorem. Thus $m$ and $f$ increase together while $n$ stays fixed. The quantity $n-m+f$ remains two, proving Euler formula for a connected planar graph.

Every facial boundary walk has length at least five. Bridge excursions can repeat an edge, but deleting those excursions leaves a boundary containing a cycle in a graph; the finite girth assumption ensures the graph is not a tree. Thus the shortest-cycle condition still gives the lower bound five even when bridges occur. Summing boundary lengths counts each edge twice, so $5f\le 2m$. Using Euler formula for a connected planar graph,Hence

The Petersen graph has ten vertices, fifteen edges, and girth five. One way to verify the girth is its description by the two-element subsets of a five-element set, with adjacency meaning disjointness. A triangle would require three pairwise disjoint two-element subsets, which is impossible. Two distinct vertices have at most one common neighbor: the only possible common neighbor is a two-element subset of the complement of their union. Therefore a four-cycle is impossible. A five-cycle exists in its standard pentagon drawing.

If it were a planar graph, part (i) would give $15\le (5/3)(10-2)=40/3$, a contradiction. Thus the Petersen graph is nonplanar. The held source has blank space where its drawing is mentioned; the named graph determines this argument without that missing illustration.

For a fixed plane embedding, place one dual vertex in each face of a plane graph and draw a dual edge across each original edge, joining its incident faces. These dual edges can be drawn without mutual crossings, so this constructs a plane dual graph. Each original vertex corresponds to a dual face of a plane graph, while each edge gives exactly one dual edge. HenceBridges give dual loops and parallel dual edges are allowed. On the sphere the dual of the resulting embedding is the original embedding, so planarity is preserved in both directions for this dual pair. The geometric dual graph is defined using an embedding; the converse is understood in that setting, rather than as a definition for an arbitrary nonplanar drawing.

Take a root $r$ with children $a,b$. Give $a$ the children $c,1$, give $c$ the children $2,3$, and give $b$ the children $4,5$. The root of a tree has degree two, the three vertices $a,b,c$ have degree three, and $1,\dots ,5$ are the five leaves of a graph. There are nine vertices and eight edges, as required by the handshaking lemma and the edge count for a tree.

A plane tree has one face of a plane graph, so its dual graph has one vertex. Every original edge is a bridge incident to that same face on both sides, so every dual edge is a loop. Thus the dual drawing in the figure is a bouquet of eight loops, arranged with the displayed nesting inherited from the tree. It has nine faces of a plane graph, matching $f^{\ast }=n=9$. The nesting matters for which faces meet; a bouquet drawn as eight unrelated petals would have a different face-adjacency graph.

Two dual faces of a plane graph share an edge exactly when their corresponding original vertices are adjacent. Their face-adjacency graph is therefore the original tree, which is a nontrivial bipartite graph. Colour the face for $r$ with one colour and alternate along the original tree. This gives a proper face colouring with two colours, and at least two are needed because there is an edge separating distinct faces. Hence the minimum is