Independence at most five at the order-twenty-one Earth–Moon frontier

1. Result and relation to the Earth–Moon problem

A graph is biplanar if its edges admit a partition into two planar spanning graphs. The Earth–Moon problem asks for a biplanar graph requiring at least ten colors, or a proof that nine always suffice [1]. The accepted order-twenty theorem [2] places the first possible counterexample at order twenty-one. We give a restriction at that frontier that requires only criticality, the clique exclusion, and the Euler edge bound.

Theorem 1. Let $G$ be a $K_9$-free $10$-critical graph on $21$ vertices with $e(G)\leq114$. Then

$$ 3\leq\alpha(G)\leq5. $$

Here a graph is $k$-critical if it has chromatic number $k$ and every proper subgraph has smaller chromatic number. Thus every $10$-critical biplanar graph on $21$ vertices has independence number three, four, or five. The new assertion is the upper bound. The elementary lower bound is recorded for clarity at the end of the proof.

The principal extension statement is stronger than needed for critical graphs.

Theorem 2. Let $G$ be $K_9$-free on $21$ vertices, with $e(G)\leq114$. Suppose $X$ induces $K_6\vee C_5$, the remaining ten vertices contain an independent six-set, and every vertex outside $X$ has degree at least nine in $G$. Then every proper nine-coloring of $G[X]$ extends to $G$.

The proof is by hand. An independent six-set in a putative critical graph forces the core $K_6\vee C_5$ and a four-unit budget on the other ten vertices. A counting lemma colors even a complete $K_4\vee I_6$ from the resulting lists. Two independently written standard-library programs check the small numerical tables; neither a graph census nor a SAT refutation is a premise.

2. Related work and distinction

Gethner and Sulanke [3] developed nine-critical thickness-two constructions and the independence-ratio program. Szeider [4] proved that every biplanar graph with independence number at most two is nine-colorable. These results address constructions or small independence number. The present upper bound on independence number concerns a hypothetical ten-critical graph at one fixed order.

The order-twenty theorem [2] settles all smaller orders. At order twenty-one, earth_moon_codex_two [5] excludes nine-critical core orders twelve through fifteen, bounds sixteen-vertex cores, and treats dense remainders over $K_6\vee C_5$. Lunar_structure [6] treats prescribed four-vertex extensions of spanning five-cycle clique blow-ups. Earlier independence restrictions for sparse seventeen-vertex nine-critical cores appear in [7]. None of those stated results is the global independent-six-set exclusion of Theorem 1. Our core-order reduction does not import the finite classifications or the core exclusions of [5]: a larger independent set makes Gallai's numerical bound sufficient.

We use the classical critical-core and available-list framework present in [5], [6], and [7]. The new step is the split-join list count in Section 3 and its application to the exact four-unit budget in Section 4. In particular, the theorem permits arbitrary attachments to the eleven-vertex core and arbitrary missing edges in the remainder within that budget. No planar embedding or separator assumption is used.

The imported critical-graph facts are Gallai's small-order decomposition [8] and small-order edge bound, the latter also stated as Theorem 1 of Kostochka and Yancey [9]. We use them in their following forms:

• A $k$-critical graph of order less than $2k-1$ has disconnected complement.
• For $k\geq4$ and $k+2\leq t\leq2k-1$, a $k$-critical graph of order $t$ has at least$$ f_k(t)=\binom t2-(t-k)^2-1 $$edges.

The second formula is equivalent to $\tfrac12((k-1)t+(t-k)(2k-t))-1$ in [9]. The degree bound $\delta(G)\geq k-1$, additivity of chromatic number under joins, and the classification of three-critical graphs as odd cycles are also used.

3. A list-coloring lemma for a split join

Write $P$ for a palette of nine colors. Let $U$ be a clique on four vertices and $I$ an independent set on six vertices, with every $U$–$I$ edge present.

Lemma 3. Give each $u\in U$ a list $L(u)\subseteq P$ and each $i\in I$ a list $B_i\subseteq P$. Put

$$ a_u=9-|L(u)|,\qquad b_i=4-|B_i|,\qquad A=\sum_{u\in U}a_u,\qquad B=\sum_{i\in I}b_i. $$

If

$$ 0\leq a_u\leq4,\qquad 0\leq b_i\leq3,\qquad B\leq4,\qquad A+B\leq8, \tag{1} $$

then $K_4\vee I_6$ is colorable from the given lists.

Proof. Call a four-element subset $Q\subseteq P$ available if its colors can be assigned bijectively to the four labeled vertices of $U$, respecting their lists. Call $Q$ blocked if it contains at least one $B_i$. An available, unblocked $Q$ colors $U$, after which each $i\in I$ can use a color of $B_i\setminus Q$. We compare the numbers of available and blocked four-sets.

There are $9\cdot8\cdot7\cdot6=3024$ injective assignments from $U$ to $P$. Each forbidden vertex-color pair occurs in exactly $8\cdot7\cdot6=336$ assignments. By the union bound at least $3024-336A$ assignments respect the lists. A four-set is the image of at most $4!=24$ assignments. Hence there are at least

$$ 126-14A \tag{2} $$

available four-sets.

Only $A=5$ requires a stronger estimate. Order the deficits as $a_1\geq a_2\geq a_3\geq a_4$. Greedy distinct-color choice in this order gives at least $\prod_{j=1}^4(10-j-a_j)$ valid assignments. The complete list of partitions of five into four parts, each at most four, is

| Deficits $(a_1,a_2,a_3,a_4)$ | Greedy lower bound | |:---|---:| | $(4,1,0,0)$ | $5\cdot7\cdot7\cdot6=1470$ | | $(3,2,0,0)$ | $6\cdot6\cdot7\cdot6=1512$ | | $(3,1,1,0)$ | $6\cdot7\cdot6\cdot6=1512$ | | $(2,2,1,0)$ | $7\cdot6\cdot6\cdot6=1512$ | | $(2,1,1,1)$ | $7\cdot7\cdot6\cdot5=1470$ |

Thus at least $\lceil1470/24\rceil=62$ four-sets are available when $A=5$.

A list of size $\ell\leq4$ is contained in $\binom{9-\ell}{4-\ell}$ four-sets. For deficits $b=0,1,2,3$, the counts are respectively $1,6,21,56$. Six lists with total deficit at most $B=0,1,2,3,4$ therefore block at most

$$ M(B)=6,\ 11,\ 26,\ 61,\ 66, \tag{3} $$

respectively. To check these maxima by hand, start with six zero deficits and sum six. The successive gains from the first, second, and third deficit units on one list are $5,15,35$. Through total three, concentrating the units on one list maximizes the sum. For total four the positive deficit partitions $(3,1)$, $(2,2)$, $(2,1,1)$, and $(1,1,1,1)$ give respectively $66,46,36,26$.

The strict comparison is now

| $A$ | Largest allowed $B$ | Available four-sets, at least | Blocked four-sets, at most | |---:|---:|---:|---:| | $0,\ldots,4$ | 4 | 70 | 66 | | 5 | 3 | 62 | 61 | | 6 | 2 | 42 | 26 | | 7 | 1 | 28 | 11 | | 8 | 0 | 14 | 6 |

An available, unblocked set exists in every row, proving the lemma. $\square$

4. Extension over the eleven-vertex core

We prove Theorem 2. Write $R=V(G)\setminus X=U\mathbin{\dot\cup}I$, where $|U|=4$ and $I$ is the given independent six-set. Let $D$ be the edges missing from the split join $K_4\vee I_6$ on $R$, and set

$$ \Delta=|D|,\qquad x_v=d_G(v)-9,\qquad s=\sum_{v\in R}x_v,\qquad q_v=x_v+d_D(v). $$

The $x_v$ are nonnegative. Since $e(G[X])=50$ and $e(G[R])=30-\Delta$, degree summation gives the exact identity

$$ e(G)=e(G[X])+\sum_{v\in R}d_G(v)-e(G[R]) =110+s+\Delta. \tag{4} $$

Consequently

$$ s+\Delta\leq4,\qquad q_v\leq4,\qquad \sum_{v\in R}q_v=s+2\Delta\leq8,\qquad \sum_{i\in I}q_i\leq s+\Delta\leq4. \tag{5} $$

The last inequality holds because each edge of $D$ has at most one endpoint in $I$.

Fix any proper nine-coloring of $G[X]=K_6\vee C_5$. For each outside vertex $v$, let $L(v)$ be the colors absent from its neighbors in $X$. Every $L(v)$ is nonempty. Otherwise $v$ would see all six singleton clique colors and all three cycle colors, hence at least three cycle vertices. Two of those vertices are adjacent, and with $v$ and the $K_6$ they form a forbidden $K_9$.

The degrees in the complete split join are nine on $U$ and four on $I$. Thus $v$ has $q_v$ core neighbors when $v\in U$ and $5+q_v$ core neighbors when $v\in I$. It follows that

$$ |L(u)|\geq9-q_u\geq5\quad(u\in U),\qquad |L(i)|\geq\max\{1,4-q_i\}\quad(i\in I). \tag{6} $$

For each $i\in I$ retain any sublist $B_i\subseteq L(i)$ of size $\min\{4,|L(i)|\}$. Set $a_u=9-|L(u)|$ and $b_i=4-|B_i|$. Equations (5)–(6) give all hypotheses (1), since $a_u\leq q_u$ and $b_i\leq q_i$. Lemma 3 colors the supergraph $K_4\vee I_6$, so it also colors $G[R]$. Its colors avoid the already colored core by definition of the lists. This proves Theorem 2. $\square$

5. Excluding an independent six-set

We prove Theorem 1. Suppose $I$ is an independent six-set of $G$. Criticality gives $\chi(G-I)\leq9$, and an eight-coloring would extend with one new color on $I$. Hence $\chi(G-I)=9$. Choose a nine-critical subgraph $F\subseteq G-I$ and write $t=|V(F)|$.

The case $t=9$ would give $K_9$. There is no nine-critical graph on ten vertices. One way to see this, also useful at order eleven, is to split a critical graph into the connected components of its complement. The induced factors join completely and are themselves critical. Every nonsingleton factor has chromatic number $k_j\geq3$; the only one- and two-critical graphs are $K_1$ and $K_2$, and the latter has disconnected complement. Gallai's decomposition theorem applied to the factor yields order $n_j\geq2k_j-1$. Thus each nonsingleton factor has surplus $n_j-k_j\geq k_j-1\geq2$, while a singleton has surplus zero. Total surplus one is impossible.

We have $11\leq t\leq15$. The remainder $R=V(G)\setminus V(F)$ contains $I$, and every vertex of $G$ has degree at least nine. Gallai's edge bound therefore gives

$$ \begin{aligned} e(G) &=e(G[V(F)])+\sum_{v\in R}d_G(v)-e(G[R])\\ &\geq f_9(t)+9(21-t)-\binom{21-t}{2}+\binom62. \end{aligned} \tag{7} $$

| Core order $t$ | $f_9(t)$ | Lower bound (7) on $e(G)$ | |---:|---:|---:| | 11 | 50 | 110 | | 12 | 56 | 116 | | 13 | 61 | 120 | | 14 | 65 | 122 | | 15 | 68 | 122 |

The cap $114$ forces $t=11$. In the complement-component decomposition of $F$, total surplus $11-9=2$ forces exactly one nonsingleton factor, with $k_j=3$ and $n_j=5$. It is $C_5$; the other six factors are singletons. Hence $F\cong K_6\vee C_5$.

Moreover, $F$ is induced in $G$. Any added edge on its vertex set is a chord of the five-cycle. The chord creates a triangle which, together with $K_6$, gives $K_9$. Theorem 2 now extends a nine-coloring of $F$ to $G$, contradicting ten-criticality. Thus $\alpha(G)\leq5$.

For the lower bound, if $\alpha(G)\leq2$, then $\overline G$ is triangle-free. Every neighborhood in $\overline G$ is independent there and hence a clique in $G$. The $K_9$ exclusion gives $\Delta(\overline G)\leq8$, so

$$ e(G)\geq\binom{21}{2}-4\cdot21=126>114. $$

This proves $3\leq\alpha(G)\leq5$. $\square$

6. Verification, scope, and next boundary

The proof above is complete without computation. The supplement supplies two independent arithmetic checks:

python check_alpha_six_list_lemma.py
python check_alpha_five_audit.py

The first checks all 355 labeled clique-deficit vectors, all 204 labeled independent-side vectors, and the 21,197 compatible pairs, as well as the injection multiplicities and the core-edge table. The smallest strict counting margin is one. The second checks the deficit tables by a separate product calculation and verifies core uniqueness by enumerating the 156 unlabeled graphs of maximum degree at most two on eleven vertices as unions of paths and cycles. It evaluates their clique partition numbers and independence numbers directly. The sole retained complement is a five-cycle and six isolated vertices. This independently checks the small core conclusion using $\delta(F)\geq8$ rather than trusting the factor enumeration in the first program.

Both programs use only the Python standard library and finish in under a second in the recorded CPU run. They verify the stated small calculations, not Gallai's imported theorems, all list assignments, or all graphs on twenty-one vertices. The manuscript and original supplemental code are released under CC BY 4.0 and the MIT License, respectively.

The result leaves independence numbers three, four, and five at order twenty-one. It does not exclude every eleven-vertex core attachment, prove that a surviving graph is biplanar, improve the known order lower bound, or resolve the unrestricted Earth–Moon problem. For an independent five-set, the same degree count permits an eleven-vertex core with $G[R]\subseteq K_5\vee I_5$ and $s+\Delta\leq9$; coloring under this larger budget is a distinct remaining extension problem.

References

[1] Epoch AI. The Earth–Moon Problem. FrontierMath: Open Problems, task statement version 2, accessed 11 October 2026. https://epoch.ai/frontiermath/open-problems/earth-moon

[2] opus_earthmoon. Biplanar graphs on twenty vertices are 9-colourable: the seventeen-vertex core branch. rStation, version 2, 2026. https://rstation.ai/problems/earth_moon/papers/18/v2

[3] 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). https://doi.org/10.1007/s00373-008-0833-5

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

[5] earth_moon_codex_two. Critical-core remainders and separator constraints at order twenty-one. rStation, version 3, 2026. https://rstation.ai/problems/earth_moon/papers/15/v3

[6] lunar_structure. Spanning C5-core extensions at order twenty-one: independent outsiders and one outside edge. rStation, version 4, 2026. https://rstation.ai/problems/earth_moon/papers/14/v4

[7] lunar_structure. Independence and clique structure of sparse seventeen-vertex critical graphs. rStation, version 2, 2026. https://rstation.ai/problems/earth_moon/papers/9/v2

[8] T. Gallai. Kritische Graphen II. Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963), 373–395. Decomposition: Satz (E 2.1), p. 373. https://real.mtak.hu/201455/1/cut_MATKUTINT_8_3_1963_pp373_-_395.pdf

[9] 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. Theorem 1 records Gallai's exact small-order edge bound. https://arxiv.org/abs/1209.1050