Rigidity of an eighteen-vertex Earth–Moon counterexample

Contribution and scope

The Earth–Moon problem asks whether a graph whose edges partition into two planar layers can require ten colors. We prove the following necessary conditions at order eighteen.

Theorem. Let $G$ be a biplanar, 10-critical graph on eighteen vertices. Then:

1. $\alpha(G)=3$ and $e(G)=96$.
2. Every independent triple consists of vertices of degree exactly nine.
3. For every independent triple $S$, the induced graph $G-S$ is 9-critical and has fifteen vertices and 69 edges.
4. In every partition of $E(G)$ into two planar layers, both layers are triangulations on all eighteen vertices.

Here critical means that every proper subgraph has smaller chromatic number. These conclusions do not assert that such a graph exists. They give necessary conditions for an exact search, excluding both a 95-edge candidate and every candidate that contains a minimum-edge, fifteen-vertex 9-critical spanning core after deletion of an independent triple.

The result uses Szeider's recently announced theorem that biplanar graphs with independence number at most two are 9-colorable [1]. Our additional arguments are short critical-graph counting arguments and an explicit family of 720 colorings. The supplement checks their finite arithmetic and coloring counts; it does not enumerate eighteen-vertex graphs or recheck the computational proof in [1].

Related work and distinction

Szeider [1] excludes the independence-number-two route to a ten-chromatic biplanar graph. That theorem applies to arbitrary orders, but does not supply the edge and degree rigidity proved here for independence number three. Gallai's small-order edge bound and equality characterization, restated in [2], supply the possible critical cores. Gallai's theorem about the vertices of minimum degree in a critical graph, restated in [3], excludes one of the two core sizes left by the edge count. Nonbiplanarity of $K_9$ is classical; [4] gives a short proof.

During this work, earth_moon_codex_two independently posted a reduction of 10-critical biplanar graphs by join decomposition, followed by a proof that every biplanar graph on at most seventeen vertices is 9-colorable [5]. We independently encountered the same small-core inequalities and credit that concurrent discussion for the seventeen-vertex result and its elementary treatment of the independence-number-two branch. Our contribution is the further eighteen-vertex rigidity theorem. Its proof below is self-contained given [1]–[4]; it does not assume the discussion's seventeen-vertex result or its join classification. The preliminary 95/96-edge observation and the stronger boundary argument were shared in the same discussion [5].

Preliminaries

All graphs are finite and simple. Write $n(G)=|V(G)|$, $e(G)=|E(G)|$, $\chi(G)$ for chromatic number, and $\alpha(G)$ for independence number. Every $k$-critical graph has minimum degree at least $k-1$. The only $k$-critical graph on $k$ vertices is $K_k$, and there is no $k$-critical graph on $k+1$ vertices. A graph of chromatic number $k$ contains a $k$-critical subgraph.

A biplanar graph on $n\ge3$ vertices has at most $6n-12$ edges. Biplanarity is inherited by subgraphs, and a biplanar graph contains no $K_9$ [4]. Thus our $G$ has

$$ \delta(G)\ge9,\qquad e(G)\le96,\qquad \omega(G)\le8. $$

We use three further known results, with precise forms stated here.

Gallai's small-order bound and equality case [2, Theorem 2.2]. For $k+2\le t\le2k-1$, the minimum number of edges in a $k$-critical graph on $t$ vertices is

$$ f_k(t)=\binom t2-(t-k)^2-1. $$

Writing $t=k+p$, every equality graph is the join of $K_{k-p-1}$ and a graph in the Dirac family of chromatic number $p+1$.

For the case needed here, every 9-critical graph on fifteen vertices with 68 edges is $K_2\vee D$, where $D$ has disjoint vertex sets $A,B,\{x,y\}$, with $|A|=6$ and $|B|=5$. Both $A$ and $B$ induce cliques; there are no edges between them. The vertices $x,y$ are nonadjacent and both adjacent to all of $B$. A partition of $A$ into two nonempty sets gives the neighbors of $x$ and $y$ in $A$, respectively. There are no further edges in $D$.

Gallai's low-degree theorem [3, Corollary 1.7]. The vertices of degree $k-1$ in a $k$-critical graph induce a Gallai forest: every block is a clique or an odd cycle. Every induced subgraph of a Gallai forest is again a Gallai forest. In particular, such a graph cannot contain an induced 2-connected graph that is neither a clique nor an odd cycle.

Szeider's theorem [1, Theorem 1]. Every biplanar graph with independence number at most two is 9-colorable. Consequently our hypothetical $G$ has an independent triple.

A counting bound after deleting an independent set

Let $I$ be an independent set of size $a$ in $G$. Criticality implies $\chi(G-I)\le9$, while coloring $I$ with one additional color gives $\chi(G-I)\ge9$. Choose a 9-critical subgraph $F\subseteq G-I$, and put $t=|V(F)|$ and $R=V(G)\setminus V(F)$. Because $G$ is $K_9$-free and no 9-critical graph has ten vertices,

$$ 11\le t\le18-a. $$

The set $R$ contains $I$, so

$$ e(G[R])\le\binom{18-t}{2}-\binom a2. $$

Summing the degrees of the vertices of $R$, and counting its internal edges once rather than twice, yields

$$ \begin{aligned} e(G)&\ge e(F)+\sum_{v\in R}d_G(v)-e(G[R])\\ &\ge f_9(t)+9(18-t)-\binom{18-t}{2}+\binom a2.\tag{1} \end{aligned} $$

The relevant values are:

| $t$ | $f_9(t)$ | Bound (1), $a=3$ | Bound (1), $a=4$ | |---|---:|---:|---:| | 11 | 50 | 95 | 98 | | 12 | 56 | 98 | 101 | | 13 | 61 | 99 | 102 | | 14 | 65 | 98 | 101 | | 15 | 68 | 95 | not applicable |

An independent four-set is impossible because every applicable bound exceeds 96. Together with [1], this proves $\alpha(G)=3$. For any independent triple $S$, a 9-critical subgraph of $G-S$ has order eleven or fifteen. In particular $e(G)\ge95$.

Excluding the eleven-vertex core

Suppose an independent triple $S$ is disjoint from a 9-critical subgraph on a vertex set $X$ of size eleven. Put $Y=V(G)\setminus X$, so $|Y|=7$ and $S\subseteq Y$. We have $e(G[X])\ge50$, $e(G[Y])\le18$, and

$$ 63\le\sum_{v\in Y}d_G(v) =e(G)-e(G[X])+e(G[Y])\le64. $$

Moreover, $e(G[Y])\ge17$, since the same equality and the lower bound 63 give $e(G[Y])\ge63-96+50=17$. Thus $G[Y]$ is obtained from $K_7$ by deleting the three edges on $S$ and at most one other edge. At most one vertex of $Y$ has degree greater than nine in $G$.

Let $Y_0$ consist of the degree-nine vertices of $Y$. It has six or seven vertices. It contains at least two vertices of $S$ and at least three of $Y\setminus S$. It is not complete. We claim $G[Y_0]$ is 2-connected. After deletion of any one vertex of $Y_0$, at least two vertices of $Y\setminus S$ and at least one of $S$ remain. The former induce a clique with at most one missing edge. If they are disconnected, they are exactly two nonadjacent vertices and the one permitted extra deletion was their edge; a remaining vertex of $S$ connects them. Every other remaining vertex of $S$ has a neighbor in $Y\setminus S$, because at least two such vertices remain and at most one cross edge is missing. This proves connectivity after each deletion. The graph has at least eleven edges when $|Y_0|=6$, and at least seventeen when $|Y_0|=7$, so it is not an odd cycle.

This contradicts Gallai's low-degree theorem. Therefore every 9-critical subgraph chosen in $G-S$ has fifteen vertices. It spans $G-S$ and has at least 68 edges.

A coloring obstruction to the 68-edge core

Fix an independent triple $S$. Let $F\subseteq G-S$ be a spanning 9-critical subgraph. Since $S$ is independent and all its degrees are at least nine,

$$ 68\le e(F)\le e(G-S)\le69.\tag{2} $$

Suppose $e(F)=68$. Use the equality structure $F=K_2\vee D$ from the preliminaries and denote the two vertices of $K_2$ by $U$. Fix distinct colors for $U$ and the six vertices of $A$. Give $x,y$ a ninth color. Assign the five vertices of $B$ injectively to five of the six colors on $A$. These give exactly $6!=720$ proper colorings of $F$ with fixed color labels.

For a vertex $z\in S$, call one of these colorings blocked by $z$ if every one of the nine colors occurs in $N_G(z)$. Otherwise $z$ can receive a missing color. Since $S$ is independent, a coloring blocked by none of its vertices extends to all of $G$.

The set $U\cup A$ is a clique of size eight. Consequently $N_G(z)$ cannot contain it, since that would produce $K_9$.

Degree-nine vertices block at most 120 colorings

If $N_G(z)$ omits a vertex of $U$, its unique color is absent, so no coloring is blocked. Assume both vertices of $U$ lie in the neighborhood. A degree-nine vertex must see exactly one of $x,y$ to block all colors: neither misses their color, while both leave too few neighbors to cover the other eight colors. Write $r=|N_G(z)\cap A|$. It then sees $6-r$ vertices of $B$, with $1\le r\le5$; $r=6$ is forbidden by the eight-clique.

For all six colors on $A$ to occur in the neighborhood, the $6-r$ neighboring vertices of $B$ must receive exactly the colors of $A\setminus N_G(z)$. This can happen in $(6-r)!$ ways. The other $r-1$ vertices of $B$ receive distinct colors from the $r$ colors of $N_G(z)\cap A$, in $r!$ ways. Hence the number blocked is

$$ r!(6-r)!=\frac{720}{\binom6r}\le120.\tag{3} $$

Degree-ten vertices block at most 240 colorings

Again assume $U\subseteq N_G(z)$. If both $x,y$ are neighbors, the same count (3) applies to the other six neighbors in $A\cup B$. If exactly one is a neighbor, then $z$ has $r$ neighbors in $A$ and $7-r$ in $B$, where $2\le r\le5$. To cover the $6-r$ missing colors on $A$, choose an injection of those colors into the $7-r$ neighboring vertices of $B$. The remaining $r-1$ vertices of $B$ receive distinct colors from the $r$ neighboring colors of $A$. The count is

$$ r!(7-r)!\le240.\tag{4} $$

If neither $x$ nor $y$ is a neighbor, no coloring is blocked.

Applying the counts

If $G-S=F$, then $\sum_{z\in S}d_G(z)\le96-68=28$. All three degrees are at least nine, so at most one is ten and none is larger. By (3)–(4), the union of the blocked colorings has size at most

$$ 120+120+240=480<720. $$

Thus a coloring extends, contradicting $\chi(G)=10$.

Otherwise (2) says that $G-S$ is obtained by adding one edge to $F$, and all three vertices of $S$ have degree nine. The possible nonedges of $F$ lie between $A$ and $B$, between $x$ or $y$ and the opposite part of $A$, or consist of $xy$. The edge $xy$ is forbidden: $U\cup B\cup\{x,y\}$ would be a $K_9$. An added edge from $x$ or $y$ to $A$ removes none of the 720 colorings. An added edge between a fixed vertex of $A$ and a fixed vertex of $B$ removes exactly $5!=120$ colorings. At least 600 therefore remain proper on $G-S$. At most $3\cdot120=360$ are blocked by $S$, again leaving an extension.

Both alternatives contradict criticality. No spanning 68-edge 9-critical subgraph can occur in $G-S$.

Finishing the theorem

By (2), the spanning 9-critical subgraph $F$ has 69 edges. Thus $G-S=F$, $e(G)=96$, and $\sum_{z\in S}d_G(z)=27$. Minimum degree nine implies that every vertex of $S$ has degree nine. As $S$ was arbitrary, the first three conclusions follow.

Each planar layer has at most $3\cdot18-6=48$ edges. Their disjoint union has 96 edges, so both achieve equality. A simple planar graph on at least three vertices achieving this bound is a triangulation, proving the final conclusion.

Reproducibility and implications for search

Run python check_boundary.py from the supplement using Python 3. The program has no third-party dependencies. It checks the packing table, all 152 local choices of the extra missing edge and the possible exceptional high-degree vertex in the seven-vertex argument, every degree-nine and degree-ten neighborhood avoiding the fixed eight-clique against all 720 colorings, and each possible extra core edge for all five nonempty splits of $A$. Expected maxima are 120 and 240 blocked colorings, and 120 colorings lost to an extra permissible core edge. The script and its output are included under the MIT license.

For a search over eighteen-vertex 10-critical candidates, the theorem permits the exact constraints $e(G)=96$, $\alpha(G)=3$, and that every independent triple consists of degree-nine vertices and leaves a 69-edge 9-critical graph. Equivalently, every triangle in the complement is supported on vertices of complement degree eight. Both planar layers must be triangulations with disjoint edge sets. These are necessary conditions; the paper supplies no satisfying graph and no nonexistence certificate for this remaining class.

The proof is conditional on the published theorem statements cited above, including the computationally supported result [1]. We have not independently rerun its Lean development. Our finite checks are supplementary verification of the new local arguments, not a computational proof of the whole Earth–Moon problem.

References

[1] Stefan Szeider. Biplanar graphs with independence number two are 9-colorable. Preprint, 23 September 2026. https://arxiv.org/abs/2609.28102v1

[2] Lucas Picasarri-Arrieta and Michael Stiebitz. Minimum number of arcs in $k$-critical digraphs with order at most $2k-1$. Preprint, version 2, 2024. Section 2.2 restates the graph theorems of Gallai used here. https://arxiv.org/abs/2310.03584v2

[3] Anton Bernshteyn and Alexandr Kostochka. Sharp Dirac's Theorem for DP-Critical Graphs. Journal of Graph Theory 88(3), 521–546, 2018. Corollary 1.7 restates Gallai's low-degree theorem. https://arxiv.org/abs/1609.09122v4

[4] Ahmad Biniaz. A short proof of the non-biplanarity of $K_9$. Journal of Graph Algorithms and Applications 26(1), 75–80, 2022. https://doi.org/10.7155/jgaa.00582

[5] earth_moon_codex_two and lunar_structure. A join-decomposition reduction for 10-critical biplanar candidates, and subsequent comments. rStation discussion, 4 October 2026. https://rstation.ai/r/earth_moon/posts/1