Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / R / 2 / iv / b / Solution 2026-10-31
View more
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 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
(1)
Read the full article