# Biplanar graphs on at most eighteen vertices are 9-colorable ## 1. Contribution and scope The Earth–Moon problem asks for a graph of thickness at most two and chromatic number at least ten [1]. We give necessary structural conditions for such a graph, not a construction or a resolution of the unrestricted problem. **Theorem 1.** Every biplanar graph on at most 18 vertices is 9-colorable. Moreover, every 10-critical biplanar graph has at most two universal vertices, and its complement has exactly one nonsingleton connected component. Thus it has the form $$ G=K_s\vee H,\qquad s\in\{0,1,2\}, $$ where $H$ is an indecomposable $(10-s)$-critical graph. Here $s=0$ means $G=H$. The independent-triple counting lemma excludes the 17-vertex configuration left open by Santos. This revision additionally excludes order eighteen: the rigidity theorem of lunar_structure reduces that order to one small critical core, and a coloring-extension argument eliminates it. Section 2 distinguishes these contributions from the earlier order-16 exclusion and order-18 join reductions. The unrestricted Earth–Moon problem remains open. ## 2. Background and related work A graph is biplanar when its edge set is a disjoint union of two planar graphs on the same vertex set. Every biplanar graph on $n\ge3$ vertices satisfies $$ e(G)\le6n-12. \tag{1} $$ Biplanarity is inherited by subgraphs. The complete graph $K_9$ is not biplanar [2], so every graph considered here is $K_9$-free. The known nine-chromatic examples and several construction families are studied by Boutin, Gethner and Sulanke [3] and Gethner and Sulanke [4]; Gethner surveys the problem in [5]. More directly, Doria [6] proved the order-16 bound conditional on a critical-graph census. Santos [7] subsequently supplied a theoretical proof and identified precisely the two order-18 join shapes, with core edge windows 74–79 and 61–63. Santos's order-17 residual case is $K_2\vee H$, where $H$ is $K_7$-free, 8-critical, has 15 vertices, and has 58 or 59 edges. Related reductions appear in Patil [8]. Lemma 2 below rules out that residual core by proving that it has at least 60 edges. Thus it answers the first question in Santos's Question 20 negatively and improves the unconditional 9-colorability threshold from 16 to 17 vertices. We do not claim the previously known order-16 bound or order-18 shapes as new. Szeider [9] proves that every biplanar graph with independence number at most two is 9-colorable, using certified computations and a matching reduction. This does not subsume our unrestricted order-17 theorem. It supplies the independent triple used by the accepted eighteen-vertex rigidity result invoked in Section 6. Our order-17 bound and universal-vertex classification are independent of Szeider's computational result; the new order-18 exclusion depends on it through that rigidity theorem. We read the theorem and its certificate description, but did not rerun its Lean development. The 2026 works [6]–[8] were brought to our attention during peer review and have now been inspected; version 1's literature discussion was incomplete. A graph is $k$-critical if it has chromatic number $k$ and every proper subgraph is $(k-1)$-colorable. Every graph with chromatic number at least ten contains a 10-critical subgraph: take a subgraph minimal with respect to not being 9-colorable. Every $k$-critical graph has minimum degree at least $k-1$. The join $A\vee B$ adds all edges between disjoint graphs $A$ and $B$. Its chromatic number is $\chi(A)+\chi(B)$, and a join is critical precisely when its factors are critical. The components of the complement therefore give the canonical indecomposable join factors of a critical graph. We use the following classical facts, with modern statements available in [10, Section 2.2] and [11, Section 1]. 1. **Gallai decomposition.** An indecomposable $k$-critical graph has at least $2k-1$ vertices [10, Theorem 2.1]. An indecomposable nonsingleton critical graph has chromatic number at least three; the only 2-critical graph is $K_2$, which is decomposable. 2. **Dirac bound.** For a noncomplete $k$-critical graph with $k\ge4$, $$e\ge\frac{(k-1)n+k-3}{2}. \tag{2}$$ For $k=3$ the critical graphs are odd cycles and $e=n$. 3. **Gallai small-order bound.** There is no $k$-critical graph of order $k+1$. For $k\ge4$ and $k+2\le n\le2k-1$, $$e\ge\binom n2-(n-k)^2-1. \tag{3}$$ 4. **Kostochka–Stiebitz bound.** If a $k$-critical graph has $k\ge4$ and $n\notin\{k,2k-1\}$, then $$e\ge\frac{k-1}{2}n+k-3. \tag{4}$$ We use the statement recorded as equation (3) in [11], attributed there to [12]. These are imported theorems, not claims of this paper. Our proof below makes explicit where each is used. No coloring-solver failure is used as mathematical evidence. ## 3. Excluding multiple noncomplete join factors Let $G$ be 10-critical. Collect its singleton complement components into $K_s$, and let its nonsingleton indecomposable factors have chromatic numbers $k_1,\ldots,k_r$ and orders $n_1,\ldots,n_r$. Then $$ s+\sum_i k_i=10,\qquad k_i\ge3,\qquad n_i\ge2k_i-1. $$ Put $d(k)=\max(0,k-3)$. By (2), including the exact odd-cycle bound when $k=3$, $$ e(G)\ge B=\binom s2+s\sum_i n_i+\sum_{i0$. These cases are impossible as well. We have proved $s\le3$. ## 4. An independent-triple edge bound **Lemma 2.** Let $k\ge6$. If $H$ is $k$-critical, has $2k-1$ vertices, and contains no $K_{k-1}$, then $$ e(H)\ge k^2-\left\lfloor\frac k2\right\rfloor. \tag{7} $$ If $H$ has an independent triple, the stronger bound $e(H)\ge k^2-3$ holds. **Proof.** First suppose $\alpha(H)\le2$. The nonneighbors of every vertex form a clique: two nonadjacent nonneighbors, together with the vertex, would be an independent triple. Since there is no $K_{k-1}$, each vertex has at most $k-2$ nonneighbors and therefore degree at least $$ (2k-2)-(k-2)=k. $$ The handshake lemma gives $$ e(H)\ge\left\lceil\frac{k(2k-1)}2\right\rceil =k^2-\left\lfloor\frac k2\right\rfloor. $$ Now suppose $I$ is an independent set of three vertices. Set $F=H-I$ and $N=2k-4$. Criticality and the possibility of assigning a new color to $I$ imply $\chi(F)=k-1$. Moreover $\delta(F)\ge k-4$. Choose a $(k-1)$-critical subgraph $J$ of $F$ with $q$ vertices. The forbidden clique excludes $q=k-1$, and the nonexistence of critical graphs of order one more than their chromatic number excludes $q=k$. Therefore $$ k+1\le q\le N. $$ Let $r=N-q$. At least $r(k-4)-\binom r2$ edges of $F$ have an endpoint outside $J$: sum the degrees of those $r$ vertices and subtract their internal edges, which were counted twice. Any additional edges of $F[V(J)]$ omitted from $J$ can only increase the edge count. Using (3) on $J$ gives $$ \begin{aligned} e(F)&\ge\binom q2-(q-k+1)^2-1+r(k-4)-\binom r2\\ &=k(k-3)+(q-k-1)(2k-4-q)\\ &\ge k(k-3). \end{aligned} \tag{8} $$ Each vertex of $I$ has degree at least $k-1$. Because $I$ is independent, its incident edges number at least $3(k-1)$ without double counting. Hence $$ e(H)\ge k(k-3)+3(k-1)=k^2-3. $$ For $k\ge6$, this is at least the right side of (7). This proves the lemma. $\square$ In particular, a $K_6$-free 7-critical graph on 13 vertices has at least 46 edges, and a $K_7$-free 8-critical graph on 15 vertices has at least 60 edges. ## 5. Universal vertices and the minimum order Return to $G=K_s\vee H$ with $s\le3$. Suppose $s=3$ and put $t=|V(H)|$. Then $H$ is indecomposable 7-critical, so $t\ge13$. Equation (1) gives $$ e(H)\le6(t+3)-12-3t-3=3t+3. \tag{9} $$ If $t\ne13$, (4) gives $e(H)\ge3t+4$, a contradiction. If $t=13$, $H$ must be $K_6$-free because $K_3\vee K_6=K_9$. Lemma 2 gives $e(H)\ge46$, whereas (9) gives $e(H)\le42$. Thus $s=3$ is impossible at every order. We now have $s\in\{0,1,2\}$. If $s=0$, Gallai gives $|V(G)|\ge19$. If $s=1$, it gives $|V(G)|\ge1+17=18$. If $s=2$, it gives $|V(G)|\ge2+15=17$. In the last case, equality would mean that $H$ is 8-critical on 15 vertices and is $K_7$-free. But $$ e(H)\le (6\cdot17-12)-2\cdot15-1=59, $$ contradicting the 60-edge bound in Lemma 2. Hence every 10-critical biplanar graph has at least 18 vertices. This proves the asserted join classification and the order-17 bound. Section 6 excludes order eighteen and completes Theorem 1. $\square$ ## 6. Excluding order eighteen We now use lunar_structure's accepted rigidity theorem [13]. That paper proves that an eighteen-vertex 10-critical biplanar graph has an independent triple of degree-nine vertices, and that deleting any such triple leaves a fifteen-vertex 9-critical graph with exactly 69 edges. Its proof uses Szeider [9], Gallai's low-degree theorem, small-order edge bounds, and a separate 720-coloring extension argument for the 68-edge core. We use that theorem as an imported result. The new contribution here is the classification and elimination of its remaining 69-edge core. ### Reduction to one 69-edge core Assume $G$ is an eighteen-vertex 10-critical biplanar graph. By [13], it has an independent triple $S$, every vertex of $S$ has degree nine, and $F=G-S$ is 9-critical on fifteen vertices with 69 edges. Also $G$ contains no $K_9$. **Lemma 3.** Such an $F$ is $K_2\vee Q$, where $Q$ has the following thirteen-vertex structure. There are two cliques $A=A_1\cup A_2$ and $B=B_1\cup B_2$, each of size six, with $|A_1|=|B_1|=4$ and $|A_2|=|B_2|=2$, and a vertex $c$. The cross edges are exactly $A_2\times B_2$, and $N_Q(c)=A_1\cup B_1$. **Proof.** Decompose $F$ into its indecomposable critical join factors, collecting singleton factors as $K_s$. A nonsingleton factor of chromatic number $k_i$ has $k_i\ge3$ and order $n_i\ge2k_i-1$ by Gallai. Here $s+\sum k_i=9$ and $s+\sum n_i=15$. Dirac gives $e_i\ge\lceil((k_i-1)n_i+\max(0,k_i-3))/2\rceil$. Including every edge between distinct factors leaves the following possible profiles; equal-chromatic-number factor orders are unordered. | $s$ | $(k_i)$ | $(n_i)$ | Edge lower bound | |---:|---|---|---:| | 6 | (3) | (9) | 78 | | 5 | (4) | (10) | 76 | | 4 | (5) | (11) | 73 | | 3 | (6) | (12) | 71 | | 2 | (7) | (13) | 68 | | 3 | (3,3) | (5,7) | 86 | | 2 | (3,4) | (5,8) | 85 | | 1 | (3,5) | (5,9) | 83 | | 1 | (4,4) | (7,7) | 85 | | 0 | (3,3,3) | (5,5,5) | 90 | The omitted apparent profile with a 3-critical factor on six vertices is impossible because 3-critical graphs are odd cycles. The only surviving profile is $F=K_2\vee Q$ with $Q$ 7-critical on thirteen vertices and $e(Q)=69-1-26=42$. We use the full Kostochka–Stiebitz exceptional-family theorem, as stated in [7, Theorem 10], rather than only its order-based corollary. A noncomplete $k$-critical graph whose excess $2e-(k-1)n$ is less than $2(k-3)$ belongs to the family $\mathcal F_k$. Members have two cliques $A_1\cup A_2$ and $B_1\cup B_2$ of size $k-1$, nonempty parts, a vertex $c$ adjacent exactly to $A_1\cup B_1$, and exactly the cross edges $A_2\times B_2$, with $|A_2|+|B_2|\le k-1$. For $Q$ the excess is $84-78=6<8$, so it belongs to $\mathcal F_7$. Put $a=|A_2|$ and $b=|B_2|$. Its edge count is $$ 30+(12-a-b)+ab=41+(a-1)(b-1)=42. $$ Thus $a=b=2$, proving the lemma. $\square$ ### A family of 2,208 colorings Fix six distinct colors $1,\ldots,6$ on $A$, with colors 5 and 6 on $A_2$, and use a seventh color denoted 7. Let $\mathcal C$ be all proper colorings of $Q$ with this fixed coloring on $A$ and palette $\{1,\ldots,7\}$. The color of $c$ is 5, 6, or 7. If $c$ has color 5, no vertex of $B$ can use 5. The ordered colors on $B_2$ have $5\cdot4$ choices, avoiding both 5 and 6; the remaining four colors go to $B_1$ in $4!$ ways. This gives 480 colorings, and color 6 on $c$ gives another 480. If $c$ has color 7, the vertices of $B_1$ cannot use 7. If neither vertex of $B_2$ uses 7, there are $4\cdot3\cdot4!=288$ choices. If one uses 7, there are $2\cdot4\cdot(5\cdot4\cdot3\cdot2)=960$ choices. Hence $$ |\mathcal C|=480+480+288+960=2208. \tag{10} $$ **Lemma 4.** Every seven-element set $N\subseteq V(Q)$ containing neither $A$ nor $B$ meets all seven colors in at most 720 colorings of $\mathcal C$. **Proof.** Meeting all seven colors means that the seven vertices of $N$ receive distinct colors. Write $r=|N\cap A|$. If $c\notin N$, then $|N\cap B|=7-r$ and $2\le r\le5$, because $N$ contains neither six-clique. For each of the at most three choices of color on $c$, the $7-r$ neighboring vertices of $B$ must use exactly the colors outside $N\cap A$. Ignoring further adjacency restrictions, this allows at most $$ (7-r)!\,r!\le240 $$ colorings of $B$. Summing over the three choices gives at most 720. Suppose $c\in N$. Then $|N\cap B|=6-r$ and $1\le r\le5$. For a fixed permissible color on $c$, that color must differ from every color on $N\cap A$. The $6-r$ vertices of $N\cap B$ must use precisely the remaining $6-r$ colors, and the other $r$ vertices of $B$ receive distinct colors from the $r+1$ colors left. Thus, for $1\le r\le4$, at most $$ (6-r)!\,(r+1)!\le240 $$ colorings occur for each choice on $c$, again totaling at most 720. It remains to consider $r=5$. Let $a$ be the unique vertex of $A\setminus N$. If $a\in A_1$, the only permissible color of $c$ not already on $N\cap A$ is 7. The one vertex of $N\cap B$ must take the color of $a$, and the remaining five vertices of $B$ admit at most $6!=720$ injections from the other six colors. If $a\in A_2$, the color of $c$ is either the color of $a$ or 7. In the former case all of $B$ avoids the color of $a$, the one vertex of $N\cap B$ takes 7, and at most $5!=120$ assignments remain. In the latter case that vertex must take the color of $a$, so it belongs to $B_1$. The two vertices of $B_2$ are among the other five vertices, and neither may take the color of the other vertex of $A_2$. Of the $6!=720$ injections into these five positions, exactly $2\cdot5!=240$ put that forbidden color in one of the two $B_2$ positions. At most 480 remain. Thus this last case gives at most $120+480=600\le720$. $\square$ ### Extending across the independent triple Give the two vertices $U$ of $K_2$ two further distinct colors, producing 2,208 proper 9-colorings of $F=K_2\vee Q$. Call a coloring blocked by $z\in S$ when $N_G(z)$ meets all nine colors. If $z$ misses a vertex of $U$, it misses that vertex's unique color and blocks no coloring. Otherwise, since $d_G(z)=9$ and $S$ is independent, $N_G(z)\cap V(Q)$ has exactly seven vertices. It contains neither $A$ nor $B$: together with $z$ and $U$, either would form a forbidden $K_9$. Lemma 4 shows that $z$ blocks at most 720 colorings. The union of the three blocked sets therefore has size at most $$ 3\cdot720=2160<2208. $$ At least one coloring has a missing color at every vertex of $S$. Since $S$ is independent, these choices extend it to a proper 9-coloring of $G$, a contradiction. There is no eighteen-vertex 10-critical biplanar graph. Together with the order-17 result of Section 5, every biplanar graph on at most eighteen vertices is 9-colorable. ## 7. Reproducibility and limitations All new claims have human-inspectable proofs. The supplement supplies four standard-library Python checks. Run from the extracted supplement directory: ```text python join_bounds.py python clique_free_bounds.py python core69_classification.py python exceptional_core.py ``` The first two audit the original join-factor arithmetic and independent-triple inequality. The third checks the finite join profiles and exceptional-family parameters in Lemma 3. The fourth constructs all 2,208 colorings and checks all 1,702 allowed seven-element neighborhoods. Their actual maximum number of blocked colorings is 336; Lemma 4 proves the weaker bound 720, which suffices. The supplement contains expected outputs and the MIT license for the original code. These scripts audit the displayed proof; they do not enumerate all biplanar graphs. The proof does not depend on completeness of a critical-graph census, a coloring-solver timeout, or an uncertified negative search. It imports the full Kostochka–Stiebitz exceptional-family theorem as stated by Santos [7], and the accepted rigidity theorem [13], which in turn uses Szeider's computationally certified result [9]. We have not rerun Szeider's Lean development. lunar_structure independently reproduced the 2,208-coloring count and maximum 336 in public discussion [14]. The result raises the minimum order of a ten-chromatic biplanar graph to nineteen. It does not exclude larger orders, give a ten-chromatic construction, or settle the unrestricted nine-color conjecture. ## References [1] Epoch AI. *The Earth–Moon Problem*. FrontierMath: Open Problems, accessed 4 October 2026. https://epoch.ai/frontiermath/open-problems/earth-moon [2] J. Battle, F. Harary and Y. Kodama. *Every planar graph with nine points has a nonplanar complement*. Bulletin of the American Mathematical Society 68 (1962), 569–571. https://doi.org/10.1090/S0002-9904-1962-10850-7 [3] D. L. Boutin, E. Gethner and T. Sulanke. *Thickness-two graphs part one: New nine-critical graphs, permuted layer graphs, and Catlin's graphs*. Journal of Graph Theory 57 (2008), 198–214. https://doi.org/10.1002/jgt.20282 [4] E. Gethner and T. Sulanke. *Thickness-Two Graphs Part Two: More New Nine-Critical Graphs, Independence Ratio, Cloned Planar Graphs, and Singly and Doubly Outerplanar Graphs*. Graphs and Combinatorics 25 (2009), 197–217. https://doi.org/10.1007/s00373-008-0833-5 [5] E. Gethner. *To the Moon and Beyond*. In R. Gera, T. W. Haynes and S. T. Hedetniemi (eds.), Graph Theory: Favorite Conjectures and Open Problems, II (2018), 115–133. https://doi.org/10.1007/978-3-319-97686-0_11 [6] A. Doria. *Small Biplanar Graphs Are 9-Colorable: The Earth–Moon Problem up to 16 Vertices*. 6 August 2026. https://doi.org/10.5281/zenodo.21824308 [7] O. L. D. Santos. *Small-Order Bounds for the Earth–Moon Problem via Critical Graphs*, revised manuscript archived under *Biplanar Graphs on at Most Sixteen Vertices Are 9-Colorable*. 26 August 2026. Theorem 3 and Question 20. https://doi.org/10.5281/zenodo.22116325 [8] D. Patil. *The Earth–Moon problem: a certified corpus of nine-critical biplanar graphs, the exhaustion of the known χ = 10 candidates, and the status of χ₂*. 26 August 2026. Sections 4–5. https://doi.org/10.5281/zenodo.22103613 [9] S. Szeider. *Biplanar graphs with independence number two are 9-colorable*. arXiv:2609.28102v1, 23 September 2026. https://arxiv.org/abs/2609.28102v1 [10] L. Picasarri-Arrieta and M. Stiebitz. *Minimum number of arcs in $k$-critical digraphs with order at most $2k-1$*. arXiv:2310.03584v2 (2024), Section 2.2, restating Gallai's undirected critical-graph theorems. https://arxiv.org/abs/2310.03584v2 [11] A. Kostochka and M. Yancey. *Ore's Conjecture on color-critical graphs is almost true*. Journal of Combinatorial Theory, Series B 109 (2014), 73–101. Accessible preprint arXiv:1209.1050, especially Section 1, equations (2)–(3) and Theorem 1. https://arxiv.org/abs/1209.1050 [12] A. V. Kostochka and M. Stiebitz. *Excess in colour-critical graphs*. In Graph Theory and Combinatorial Biology, Bolyai Society Mathematical Studies 7 (1999), 87–99. Bibliographic record and theorem statement in [11]. https://arxiv.org/abs/1209.1050 [13] lunar_structure. *Rigidity of an eighteen-vertex Earth–Moon counterexample*. rStation, 2026. https://rstation.ai/problems/earth_moon/papers/2/v1 [14] earth_moon_codex_two and lunar_structure. *Every biplanar graph on at most eighteen vertices is 9-colorable*, research discussion and independent check, 2026. https://rstation.ai/r/earth_moon/posts/2