Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 1 / 17F (Graph Theory)

Euler characteristic for a finite connected plane graph is $v-e+f=2$. For a simple connected planar graph with $v\ge 3$, each facial boundary has length at least three and the total boundary length is $2e$, so $3f\le 2e$. Combining gives $e\le 3v-6$, and therefore average degree of a graph $2e/v<6$. Some vertex has degree at most five. Components of size one or two have this property directly, so every nonempty finite simple planar graph has $\delta (G)\le 5$.

Prove five colour theorem by induction on vertex count. Remove a vertex $x$ of degree at most five and colour the remaining planar graph with five colours. If its neighbours use fewer than five colours, assign an unused colour to $x$. Otherwise its five neighbours $x_1,\dots ,x_5$ occur in cyclic order around $x$ with colours $1,\dots ,5$. If no path of colours $1,3$ connects $x_1$ to $x_3$, interchange these colours in the component of $x_1$, freeing colour 1 at $x$.

If such a path exists, a simple path together with $x{x}_1$ and $x{x}_3$ makes a Jordan curve. The cyclic order puts $x_2$ and $x_4$ on opposite sides. A path of colours $2,4$ between them would have to cross the curve, impossible in the plane embedding; it cannot meet the differently coloured path or use the removed vertex. Interchange colours $2,4$ in the component of $x_2$, freeing colour 2 at $x$. The colouring extends in every case. Thus $\chi (G)\le 5$ for finite simple planar graphs. The usual simple-graph convention is needed: loops would invalidate a proper-colouring assertion.

False. The complete bipartite graph $K_{3,3}$ has chromatic number two, but is nonplanar. For example a simple bipartite plane graph has $e\le 2v-4$, because all facial cycles have length at least four; $K_{3,3}$ has $v=6$, $e=9>8$.

False. Attach 594 pendant vertices to one vertex of $K_{3,3}$. The connected graph still contains the nonplanar $K_{3,3}$, but has $v=600$, $e=603$, and average degree of a graph $2e/v=2.01$. Attaching more leaves lowers the average further toward two without making the graph planar.

True for finite connected simple graphs. average degree of a graph at most two implies $e\le v$. A spanning tree has $v-1$ edges, leaving at most one extra edge. Hence the graph is a tree or unicyclic. trees are planar, and a unicyclic graph is a cycle with trees attached to its vertices, which can also be embedded in the plane. Connectedness is essential to this argument: a disconnected nonplanar component can be diluted by isolated vertices.