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

For a finite connected plane graph, with $v$ vertices, $e$ edges and $f$ faces including the unbounded face, Euler formula for a connected planar graph isIf the graph is a tree, $e=v-1$ and $f=1$. Otherwise remove an edge on a cycle. This preserves connectivity and joins the two faces on its sides, so both $e$ and $f$ decrease by one. Repeating reaches a tree, preserving $v-e+f$ throughout and proving the formula.

For a simple connected graph with $v\ge 3$, each face boundary walk has length at least three, with bridges counted twice in the walk; the sum of lengths is $2e$. Hence $3f\le 2e$, which with Euler gives $e\le 3v-6$. If it has no triangles in a graph, no face boundary walk can have length three, and every boundary length is at least four. Thus $4f\le 2e$, givingFor a disconnected graph, add noncrossing bridges between its components; this preserves simplicity and creates no triangles, reducing to the connected bound.

Every triangle-free planar graph with at least three vertices has average degree $2e/v<4$, and therefore a vertex of degree at most three. Remove one such vertex. Its remaining graph is again triangle-free and planar. Induction, with graphs on at most two vertices as the base cases, provides a graph colouring with four colours of the remainder. At most three colours appear on the removed vertex's neighbours, so a fourth colour extends the graph colouring. This proves four-colourability without using the four-colour theorem.