Past exam of the probability, statistics and options I course of the University of Oxford / 2011 / R / 1

The complete bipartite graph $K_{3,3}$ is not a planar graph. For example, a simple connected triangle-free planar graph with six vertices has at most $2\cdot 6-4=8$ edges, by Euler formula for a connected planar graph and the fact that every face has boundary length at least four; $K_{3,3}$ has nine edges. At least one edge must therefore be deleted.

Delete $a_3{b}_3$ from the bipartition $\{a_1,a_2,a_3\}\bigsqcup \{b_1,b_2,b_3\}$. The left drawing below is a planar embedding of all eight remaining edges. It proves that the minimum is one edge.

The complete bipartite graph $K_{2,3}$ is connected and has five vertices and six edges. It is a planar graph, as in the right drawing above. Euler formula for a connected planar graph therefore givesThis includes the unbounded exterior face.

Within each connected component with $n_i$ vertices, grow a tree by starting at one vertex and repeatedly adding an edge to an unreached vertex. Connectedness guarantees such an edge until every vertex has been reached. Exactly $n_i-1$ edges are added, so the component contains at least that many edges. Summing over the $k$ components givesThe selected trees form a spanning forest, and equality holds precisely when the original graph itself is a forest.

Use the convention that $W_n$ is the wheel graph with rim $C_n$ and one additional hub; the assumption $n\ge 3$ gives the rim at least three vertices. The rim needs two colours for even $n$ and three for odd $n$. Since the hub is adjacent to every rim vertex, its colour must be a new one. These lower bounds are attained by properly colouring the rim and adding that extra colour. ThusIf a convention indexes a wheel by its total number of vertices instead, replace the rim size $n$ by $n-1$ in this formula.