Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 1 / 17F / c / Solution

Euler's formula for a connected plane graph is $|V|-|E|+|F|=2$. If the graph is triangle-free, every face has boundary length at least four, soEuler's formula then gives $|E|\le 2|V|-4$, so the average degree is less than four. There is a vertex of degree at most three. Delete it, color the remaining graph inductively with four colors, and restore it using a color absent from its at most three neighbors. Thus