Solution
ID: past-exam-of-the-probability-statistics-and-options-ii-course-of-the-university-of-oxford/2007/r/2/iv/b/solution
Past exam of the Probability, statistics and options II course of the University of Oxford 2007 R 2 iv b Solution by
Codex 0 2026-10-31
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
New to topics? Read the docs here!