Biplanar Graphs on at Most Sixteen Vertices Are 9-Colorable

A graph is biplanar if its edge set can be partitioned into two planar graphs, and the Earth–Moon problem asks for the largest chromatic number χ₂ of a biplanar graph. Kirchweger, Scheucher and Szeider determined by SAT-based exhaustive search which biplanar graphs of small order admit a given chromatic number; their table of the state of knowledge leaves eleven cells open for n ≤ 19. We show that classical bounds on the number of edges of a color-critical graph settle eight of those eleven cells. Writing χ₂(n) for the maximum chromatic number of an n-vertex biplanar graph, we prove χ₂(n) ≤ 9 (n ≤ 16), χ₂(n) ≤ 10 (n ≤ 20), χ₂(n) ≤ 11 (n ≤ 88), so that χ₂(n) = 9 for 11 ≤ n ≤ 16. The proofs use no graph enumeration and no planarity computation. The engine is an observation about which critical graphs can be biplanar at all. Dirac's excess bound is attained only on a family of critical graphs on 2k−1 vertices, and the Kostochka–Stiebitz theorem doubles the bound off an explicit exceptional family F_k; every member of F_k contains a clique on k−1 vertices and has independence number 2. Since K₉ is not biplanar, a k-critical biplanar graph with k ≥ 10 can never lie in that family, and the same forbidden clique is inherited by every critical core arising below, so the strengthened bound is available throughout. The 12-chromatic threshold falls to the same principle in a different guise: the extremal graphs of the Kostochka–Yancey density bound are exactly the k-Ore graphs, and every k-Ore graph contains K_{k−1}, so no biplanar critical graph is extremal and the sharper non-Ore bound applies. The two inputs are complementary rather than nested: the exceptional-family argument is the stronger one for χ = 10 and χ = 11, the density bound for χ = 12. Of the three cells that remain open, the first two reduce to three explicitly parametrised critical cores; the order-19 case lies beyond Gallai's small-order decomposition.