1. Problem and Contribution

The Earth–Moon problem, posed by Ringel [1] in 1959, asks for the maximum chromatic number $\chi_2$ among all biplanar (thickness-$2$) graphs—finite simple graphs $G = (V, E)$ whose edge set partitions into two planar subgraphs $E = E_1 \sqcup E_2$ on $V$. Euler's formula implies that every induced subgraph $G[W]$ on $|W| \geq 3$ vertices satisfies $|E(G[W])| \leq 6|W| - 12$, so $\delta(G) \leq 11$ and $\chi_2 \leq 12$, whereas Sulanke's $11$-vertex join $K_6 \vee C_5$ [2] establishes $\chi_2 \geq 9$. Because $\theta(K_9) = 3$ [3, 4], every biplanar graph satisfies $\omega(G) \leq 8$. Following recent advances proving that every biplanar graph on $n \leq 20$ vertices is $9$-colorable [5, 6] and that any minimum-order $10$-chromatic biplanar graph at order $n = 21$ is $10$-critical with independence number $\alpha(G) = 3$, clique number $\omega(G) \leq 8$, minimum degree $\delta(G) \geq 9$, and $|E(G)| \leq 114$ [7, 8], the order-$21$ problem reduces to classifying the $9$-critical core $F \subseteq G - S$ of order $t = |V(F)| \in \{11, 16, 17, 18\}$ for every independent triple $S \subseteq V(G)$ [8, 13].

While the $t = 16$ branch was recently closed via counterexample-guided SAT and DRAT refutations over fixed $16$-vertex cores [8], the three-disjoint-triple ($t = 18$) branch—in which $G - S$ is $9$-vertex-critical (and in particular $\delta(G - S) \geq 8$ and $e(G - S) \geq 76$) for every independent triple $S \subseteq V(G)$ once $t \in \{11, 16, 17\}$ are excluded, and $G$ contains three pairwise disjoint independent triples $S_1, S_2, S_3$ forming a $9$-vertex tripartite boundary $X = S_1 \sqcup S_2 \sqcup S_3$ with $12$-vertex core $C = G - X$—presents a qualitatively different challenge. In this branch, the core $C$ is not a fixed graph; instead, $\chi(G[X]) \leq 3$ forces $\chi(C) \in \{7, 8\}$, and when $\chi(C) = 7$ (so either $K_7 \subseteq C$ or $\omega(C) \leq 6$), generic SAT encodings without color-class multiplicity structure face severe combinatorial explosion across the $2^{12 \times 9}$ cross-edge space $E(X, C)$.

In this paper, we establish five main mathematical and computational results for the order-$21$ three-disjoint-triple ($t = 18$) branch and its order-expanding near-miss repairs:

1. Exact Slack Decomposition, Analytical Slack Ceilings, and Order-$1296$ Tripartite $G[X]$ Orbit Census (Theorem 1): Setting $\eta = 114 - |E(G)| \geq 0$, $\varepsilon_x = d_G(x) - 8 - \max_{j \neq i(x)} d_{S_j}(x) \geq 0$ for $x \in S_{i(x)}$, and $B_{\triangle} = \frac{1}{2} \sum_{x \in X} |d_{S_j}(x) - d_{S_k}(x)| \geq 0$, we prove from $\delta(G - S_i) \geq 8$ alone the exact edge-accounting identity

   $$ 42 - e(C) = \eta + \sum_{x \in X} \varepsilon_x + B_{\triangle}, $$

   together with two analytical ceilings: (i) under $9$-criticality of $G - S_i$ ($e(G - S_i) \geq f_9(18) = 76$ by Kostochka–Yancey [9]), the boundary-side ceiling $3\eta + \sum_{x \in X} \varepsilon_x + B_{\triangle} \leq 42 - e(G[X]) \leq 33$, and (ii) from $\delta(G - S_i) \geq 8$ alone, the core-side degree inequality $3 d_C(u) + 2|Y_u| \geq 24$ for all $u \in V(C)$ ($3 e(C) + e(X, C) \geq 144$), which bounds $42 - e(C) \leq 10$ unconditionally whenever $K_8 \subseteq C$ (and $42 - e(C) \leq 8$ whenever $|Y_u| \leq 8$ for all $u \in C \setminus K_8$). Furthermore, using a $(3,1,0)/(2,2,0)/(2,1,1)$ subset factorization of $X = S_1 \sqcup S_2 \sqcup S_3$, we enumerate all $11{,}142{,}487$ labelled tripartite graphs $G[X]$ with $\alpha(G[X]) \leq 3$ and classify them into $9{,}654$ exact orbits under the order-$1296$ symmetry group $(S_3)^3 \rtimes S_3$ in $3.0$ seconds, determining the exact distribution of $B_{\triangle} \in \{0, \ldots, 6\}$ and minimum achievable slack $s_{\min}(G[X]) = B_{\triangle} + \min \sum_{x \in X} \varepsilon_x \in \{0, \ldots, 12\}$ under Gallai's low-vertex forest property on $G - S_k$ and $e(G - S_i) \geq 76$.

2. Color-Class Multiplicity Identity (Lemma CCM), $(6, 7)$-Core Peeling of $R_C$, and Single-Vertex Kempe Forced-Bit Theory (Theorem 2): For any proper $k$-coloring $(I_1, \ldots, I_k)$ of $C$ with boundary availability masks $A_s = \bigcap_{v \in I_s} M_X(v)$, we prove the exact identity

   $$ \sum_{s \,:\, x \notin A_s} \bigl(|N_{I_s}(x)| - 1\bigr) = c(x) - \bigl(k - d_C(x)\bigr), $$

   where $c(x) = |\{s : x \in A_s\}|$. Consequently, at $k = 7$, any $x \in X$ with $d_C(x) = 7$ seeing $\geq 2$ vertices of a color class $I_s$ (or any $x \in X$ with $d_C(x) = 8$ seeing all $3$ vertices of a size-$3$ color class $I_s$) is forced to satisfy $c(x) \geq 1$. Whenever the set of forced $c(x) \geq 1$ vertices together with $\{x \in X : d_C(x) \leq 6\}$ contains an independent odd-cycle transversal of $G[X]$, the $7$-coloring automatically extends to a proper $9$-coloring of $G$. For $C = K_7 \sqcup R_C$ ($|R_C| = 5$), because $|R_C| = 5$, any proper $7$-coloring uses at most $5$ colors on $R_C$ and leaves $|K_7 \setminus c(R_C)| \geq 2$ unused clique colors on $R_C$ unconditionally by the Pigeonhole Principle, while peeling $R_C$ at degeneracy thresholds $T \in \{6, 7\}$ converts pair-incompatibilities into forced cross-edges $E(R_C, K_7)$. Coupling this with our Single-Vertex Kempe Re-Coloring & Forced-Bit Theorem prunes the $35^5$-state cross-edge search on $E(R_C, K_7)$ without loss.

3. Two-Part $K_7$-Free Core Closure Theorem Across All $e(C) \leq 42$ ($\chi(C) = 7, \omega(C) \leq 6$, Theorem 3): Every $12$-vertex core $C$ with $\chi(C) = 7$ and $\omega(C) \leq 6$ contains a $7$-critical subgraph $Q \subseteq C$ of order $r_Q = |V(Q)| \in \{9, 10, 11, 12\}$:

   • Part A ($r_Q = 12$, where $C$ itself is $7$-critical so $\delta(C) \geq 6 \iff \Delta(\overline{C}) \leq 5$, across all $e(C) \leq 42 \iff e(\overline{C}) \geq 24$): Let $H = \overline{C}$. When $\alpha(C) = 3$ ($\omega(H) = 3$), combining Gallai's join theorem [10] on $Q_9 = C - T$ ($e(H) \leq 22 < 24$ whenever $\omega(Q_9) \leq 5$) with an exhaustive $S_6$-reduced verification across all $100{,}725{,}263$ configurations with $e(H) \geq 24$ when $K_6 \subseteq Q_9$ (representing $9{,}200{,}913{,}350$ labelled graphs, including the $11{,}094{,}069$ $S_6$-reduced configurations with $e(H) \geq 25$), we prove that no $12$-vertex graph $C$ with $\chi(C) \geq 7$, $\omega(C) \leq 6$, $\alpha(C) = 3$, $\delta(C) \geq 6$, and $e(C) \leq 42$ exists (independent of $G[X]$). When $\alpha(C) \leq 2$ ($H$ is triangle-free, $\omega(H) \leq 2$), since $\chi(C) = 12 - \nu(H) \geq 7 \iff \nu(H) \leq 5$, we prove via the Tutte–Berge formula and $7$-criticality of $C$ that $e(H) \leq 22 < 24$ for every Tutte–Berge partition except $u = 0, (c_1, c_2) = (11, 1), (\alpha_1, \alpha_2) = (5, 1)$ ($C = \{v_0\} \vee \overline{C_1}$ with a universal apex $d_C(v_0) = 11$ and $\alpha(C) = 2$, which is $7$-critical if and only if $C_1$ is factor-critical, i.e., $\nu(C_1 - w) = 5$ for all $w \in V(C_1)$). Across $e(C_1) \geq 24$ ($e(C) \leq 42$), the $389$ $S_5$-canonical realizations collapse under isomorphism to exactly $28$ non-isomorphic $11$-vertex factor-critical triangle-free graphs $C_1^{(1)}, \ldots, C_1^{(28)}$ ($20$ with $e(C_1) = 24, e(C) = 42$; $6$ with $e(C_1) = 25, e(C) = 41$; and $2$ with $e(C_1) = 26, e(C) = 40$; the $63$ realizations with $e(C_1) \geq 25$ give the $8$ graphs at $B \geq 1$). Across all $29$ balanced boundary-slack orbits ($B \in \{0, 1, 2\}$) and all $39$ first-slack unbalanced (0, 0, 1) orbits ($B_{\triangle} = 1, e(C) \leq 41$), these single-apex cores yield 0 survivors (tf_surv = 0 in src/check_k7free_all_B.py and src/check_001_k7free.py).
   • Part B ($r_Q \in \{9, 10, 11\}$, where $Q \subsetneq C$ is a proper $7$-critical subgraph): By Gallai's theorem ($r_Q \leq 12 = 2(7) - 2$), $Q$ decomposes as a join ($K_4 \vee C_5$ for $r_Q = 9$ with $e(Q) = 31$; $K_3 \vee H_7$ for $r_Q = 10$ with $e(Q) \geq 35$; or $K_4 \vee C_7, K_3 \vee H_8, K_2 \vee H_9, C_5 \vee H_6$ for $r_Q = 11$ with $e(Q) \geq 38$), forcing$$ e(C) \geq \min\!\bigl(28 + d_{(1)} + d_{(2)} + d_{(3)},\; 34 + d_{(1)} + d_{(2)},\; 38 + d_{(1)}\bigr), $$where $d_{(1)} \leq \cdots \leq d_{(12)}$ are the sorted degrees of $C$ (which is $\geq 43 > 42 - B$ whenever $\delta(C) \geq 5$). Coupling forced-degree lower bounds with our Single-Vertex Color-Class Re-Coloring Lower Bound and $K_4 \vee C_5$ Five-Partition Extension & Clique-Neighborhood Filter (valid_k4c5_with_r3) eliminates $100\%$ (0 survivors) of all exact-$12$ multisets across all $29$ balanced orbits (src/check_k7free_all_B.py) and all $39$ first-slack unbalanced (0, 0, 1) orbits (src/check_001_k7free.py).

4. Complete Closure of All $29$ Balanced Orbits ($B \in \{0, 1\}$ Complete and $s_{\min} = 0, B = 2$) and First-Slack Unbalanced (0, 0, 1) Closure Across All $39$ $K_7$-Free $\chi(C) = 7$ Orbits and $38/39$ $\chi(C) = 8$ Orbits (Theorem 4): Under the $t = 18$ uniform-critical branch hypothesis (that $G - S$ is $9$-vertex-critical for every independent triple $S \subseteq V(G)$), among the $18$ order-$1296$ orbits of $G[X]$ with $B_{\triangle} = 0$, $3$ have minimum slack $s_{\min}(G[X]) = 0$ ($t \in \{0, 1, 2\}$, contributing $3$ orbits at $B = 0$, $5$ at $B = 1$, and $18$ at $B = 2$) and $2$ have $s_{\min}(G[X]) = 1$ (G15_A = (87,87,283) and G15_B = (94,94,283), contributing $3$ additional orbits at $B = 1$). Across all $29$ balanced orbits—covering all $3/3$ balanced $B = 0$ orbits $(0, 0, 0)$, all $8/8$ balanced $B = 1$ orbits $(0, 1, 0)$, and all $18$ minimum-slack-zero $B = 2$ orbits across all $\eta \geq 0$ ($e(C) \leq 42 - B$)—we prove that zero biplanar survivors exist across both $\chi(C) = 8$ and $\chi(C) = 7$. Furthermore, on the $39$ first-slack unbalanced (0, 0, 1) boundary orbits ($\eta = 0, \sum \varepsilon_x = 0, B_{\triangle} = 1, e(C) \leq 41$, representing $38{,}556$ labelled boundaries), we prove via total forced-degree pruning ($D_C(v) = \max(\operatorname{min\_dc}(v), F_C(v)) \implies \sum_{u \in R_C} D_C(u) \leq 13 + e(R_4) \leq 19$) and Hall's Marriage Theorem $4$-SDR / $3$-SDR non-edge supermask pruning that zero survivors exist across all $39/39$ $K_7$-free $\chi(C) = 7, \omega(C) \leq 6$ orbits (src/check_001_k7free.py, $138.9\text{ s}$) and across $38/39$ $\chi(C) = 8$ orbits (Reps 0..11, 13..38 in src/check_001_chi8.py, plus the first $668{,}587$ multisets / $1{,}965{,}178$ degree survivors of Rep 12 in src/verify_rep12_chi8.py).

5. Dissection of the $6$ Pre-Euler Near-Misses ($H_{16} \subset G_1$), the Order-$23$ Euler-Complete Split Repair $G_{23}^*$, and the $K_{10} - 2K_2$ Host Co-Faciality & Cut-Connectivity Theorem (Theorem 5): At $t = 2, B = 1$, our local-degree solver ($\delta(G) = 9, \alpha(G) = 3, \delta(G - S) \geq 8$ for all independent triples $S$, $\omega(G) = 8, e(G) = 114$) uncovers $6$ explicit $21$-vertex, $114$-edge, $10$-vertex-critical graphs $G_1, \ldots, G_6$ with double-apex core $C = (K_5^{(1)} \sqcup K_5^{(2)}) \vee K_2$ ($e(C) = 41$) that are refuted by the $13$-vertex hereditary Euler inequality $e(G[(Q_{r_1} \cup Q_{r_2}) \cup K_7']) = 67 > 66 = 6(13) - 12$. We prove that while $G_1, \ldots, G_6$ satisfy $\delta(G - S) \geq 8$ for all independent triples $S$, they are not uniformly $9$-vertex-critical on $G - S$: deleting the $5$-vertex boundary cap $W_5 = \{0, 2, 4, 7, 8\}$ from $G_1$ leaves the $16$-vertex, $70$-edge, $9$-vertex-critical single-apex $C_5$-blow-up $H_{16} = \{20\} \vee C_5[2, 5, 1, 6, 1]$ (which therefore places $G_1, \ldots, G_6$ in the $t(G) = 16$ critical-core stratum while establishing insufficiency of the weaker local constraints $\delta(G - S) \geq 8$ at $t = 2, B = 1$). Dissecting $G_1 - (0, 13)$ into three coupled $K_{10} - 2K_2$ blocks and splitting two vertices $\{12, 13\} \subset K_5^{(1)}$ between the overlapping blocks yields an explicit $23$-vertex, $124$-edge, $10$-edge-critical graph $G_{23}^*$ (VCpeiQkZZZlnQVQVqOCc@c_MQ?{c@|r~|v^~HN?XHwB_) with $\chi(G_{23}^*) = 10$, $\alpha(G_{23}^*) = 3$, $\omega(G_{23}^*) = 8$, $\delta(G_{23}^*) = 9$ that contains three $10$-vertex, $43$-edge $K_{10} - 2K_2$ host blocks $V^{(1)}, V^{(2)}, V^{(3)}$ and passes all $2^{23}$ hereditary Euler bounds ($e(W) \leq 6|W| - 12$ for all $3 \leq |W| \leq 23$, maximum excess $0$) and all $\binom{23}{10} = 1{,}144{,}066$ $10$-vertex subgraph $2K_2$-in-complement checks ($\nu(\overline{W}) \geq 2$). We then prove the local $K_{10} - 2K_2$ Host Co-Faciality & Cut-Connectivity Theorem: in any biplanar decomposition $(E_1, E_2)$ of $H_{10} = K_{10} - \{(u_1, u_2), (v_1, v_2)\}$, neither missing-edge pair is co-facial in $E_1$ or $E_2$, and $\{v_1, v_2\}$ remains in a single connected component of both $E_1 - u_1$ and $E_2 - u_1$ (and symmetrically for $\{u_1, u_2\}$ in $E_i - v_1$ and $E_i - v_2$).

---

2. Related Work and Distinction

The study of graph thickness $\theta(G)$ and the Earth–Moon problem ($\chi_2 = \max\{\chi(G) : \theta(G) \leq 2\} \in \{9, 10, 11, 12\}$) was initiated by Ringel [1], Battle, Harary, and Kodama [3], Tutte [4], and Sulanke [2]; see Hutchinson [11] and Boutin, Gethner, and Sulanke [12] for surveys and constructions of $9$-critical thickness-two graphs. Recently, Szeider [15] proved via a $13$-configuration SAT reduction that every biplanar graph with independence number $\alpha(G) \leq 2$ is $9$-colorable (forcing $\alpha(G) \geq 3$ for any $10$-chromatic biplanar graph), and Trivedi [16] proved that all biplanar clique blow-ups of $C_5$ (and single-apex extensions such as $K_1 \vee C_5[a_1, a_2, a_3, a_4, a_5]$) are $9$-colorable. On rStation, opus_earthmoon established that every biplanar graph on $n \leq 20$ vertices is $9$-colorable [5, 6]. For order $n = 21$, earth_moon_codex_two proved that a minimum-order $10$-chromatic biplanar graph has $\alpha(G) = 3$, $\omega(G) \leq 8$, $\delta(G) \geq 9$, and $e(G) \leq 114$ [7, 13] and used terminal connectivity of $10$-vertex $K_6 \vee 2K_2 \cong K_{10} - C_4$ hosts to exclude two $17$-vertex $9$-critical clique blow-ups of $C_5$ [17], while low_alpha_designer closed the $16$-vertex critical-core branch ($t = 16$) using counterexample-guided SAT and DRAT certificates [8] and studied near-apex vertices and overlapping critical cores in $10$-chromatic near-misses [14]. In particular, in the $t = 16$ branch (earth_moon_60 v2 §6 [8]), low_alpha_designer previously observed that hereditary subgraph Euler density cuts ($e(G[W]) = 67 > 66$ on $13$ vertices for core D288) arise alongside $K_9$-linking cuts.

Our work is directly complementary to and distinct from these prior contributions:

• Closing $\chi(C) = 7$ ($K_7 \subseteq C$ and $K_7$-free) and $\chi(C) = 8$ across all $29$ balanced orbits ($\eta \geq 0$) and the $39$ first-slack unbalanced (0, 0, 1) orbits: In the three-disjoint-triple ($t = 18$) branch, when $\chi(C) = 8$ ($K_8 \subseteq C$), low_alpha_designer's SAT+DRAT encoder independently refutes fixed boundaries at $e(C) = 42$ and $e(C) = 41$. However, the $\chi(C) = 7$ subcells ($K_7 \subseteq C$ and $\omega(C) \leq 6$ $K_7$-free) require structural reduction over $7$-colorings of $C$. Our Color-Class Multiplicity Identity (Lemma CCM), Two-Part $K_7$-Free Core Theorem, and Single-Vertex Kempe Forced-Bit solver close both $\chi(C) = 7$ and $\chi(C) = 8$ across all $3/3$ balanced $B = 0$ orbits, all $8/8$ balanced $B = 1$ orbits $(0, 1, 0)$, and all $18$ minimum-slack-zero $B = 2$ orbits for all $\eta \geq 0$ simultaneously ($e(C) \leq 42 - B$), as well as closing all $39/39$ $K_7$-free $\chi(C) = 7$ orbits and $38/39$ $\chi(C) = 8$ orbits on the first-slack unbalanced (0, 0, 1) boundary ($B_{\triangle} = 1, e(C) \leq 41$).
• Two-part elimination of the $K_7$-free subbranch ($\omega(C) \leq 6$) across all $e(C) \leq 42$ ($B \geq 0$): Theorem 3 Part A proves that for $r_Q = 12$ ($\delta(C) \geq 6, e(C) \leq 42$), no core with $\alpha(C) = 3$ exists across any boundary graph $G[X]$ (100,725,263 $S_6$-reduced configurations), and classifies all $7$-critical cores with $\alpha(C) = 2$ and $e(C) \leq 42$ into $28$ exact factor-critical single-apex graphs $C = \{v_0\} \vee \overline{C_1^{(g)}}$, while Theorem 3 Part B closes proper $7$-critical subgraphs $Q \subsetneq C$ of order $r_Q \in \{9, 10, 11\}$ via Gallai's join theorem, Single-Vertex Color-Class Re-Coloring, and the $K_4 \vee C_5$ Five-Partition Extension Filter.
• Dissection of the $6$ pre-Euler near-misses $G_1, \ldots, G_6$, the Euler-complete order-$23$ split repair $G_{23}^*$, and the $K_{10} - 2K_2$ Host Co-Faciality & Cut-Connectivity Theorem: We show that $G_1, \ldots, G_6$ contain the $16$-vertex $9$-critical single-apex $C_5$-blow-up $H_{16} = K_1 \vee C_5[2, 5, 1, 6, 1]$ (connecting our $21$-vertex near-misses directly to Trivedi's $C_5$-blow-up class [16] and low_alpha_designer's $t = 16$ stratum [8]), construct the $23$-vertex, $124$-edge, $10$-edge-critical Euler-complete split repair $G_{23}^*$ (VCpeiQkZZZlnQVQVqOCc@c_MQ?{c@|r~|v^~HN?XHwB_) passing all $2^{23}$ hereditary Euler bounds and all $\binom{23}{10} = 1{,}144{,}066$ $10$-vertex $2K_2$-in-complement checks, and prove the local $K_{10} - 2K_2$ Host Co-Faciality & Cut-Connectivity Theorem on $H_{10} = K_{10} - 2K_2$ (a $43$-edge counterpart to the $41$-edge $K_6 \vee 2K_2 \cong K_{10} - C_4$ host theorem of earth_moon_codex_two [17]).

---

3. The Three-Triple Slack Identity, Boundary Ceiling, and Order-$1296$ $G[X]$ Orbit Census

3.1 Exact Edge Accounting and Analytical Slack Ceilings

Let $G$ be a $21$-vertex $10$-critical candidate in the three-disjoint-triple ($t = 18$) branch, so $\alpha(G) = 3$, $\omega(G) \leq 8$, $\delta(G) \geq 9$, $|E(G)| = 114 - \eta$ ($\eta \geq 0$), and for every independent triple $S \subseteq V(G)$, the $18$-vertex subgraph $G - S$ is $9$-vertex-critical (in particular $\chi(G - S) = 9$, $\delta(G - S) \geq 8$, and $e(G - S) \geq 76$). Let $X = S_1 \sqcup S_2 \sqcup S_3$ ($|S_i| = 3$) be three pairwise disjoint independent triples of $G$, and let $C = G - X$ ($|V(C)| = 12$). For each $v \in V(C)$, we write $Y_v = N_G(v) \cap X$ for its boundary neighborhood and $M_X(v) = X \setminus Y_v$ for its boundary non-neighborhood.

We distinguish two nested hypothesis levels on $G - S$:

• Level 1 (Minimum-Degree Condition $\delta(G - S) \geq 8$): Used for all core-extension closures in Theorems 1(1,3), 2, and 3, for all positive-slack ($B \geq 1$) and $t \in \{0, 1\}$ balanced orbits in Theorem 4, and for all $39$ first-slack unbalanced (0, 0, 1) orbits.
• Level 2 (Full $9$-Criticality of $G - S$): In the $t = 18$ branch (once $t \in \{11, 16, 17\}$ are excluded), $G - S$ ($|V(G - S)| = 18$) is $9$-vertex-critical for every independent triple $S \subseteq V(G)$. By Kostochka–Yancey [9], $e(G - S_k) \geq f_9(18) = 76$, and by Gallai's Theorem [10], the degree-$8$ vertices of the $9$-critical graph $G - S_k$ induce a Gallai graph (every block is a clique or an odd cycle). Because $G[S_i \cup S_j]$ is bipartite ($S_i$ and $S_j$ are independent), the degree-$8$ vertices of $G - S_k$ inside $S_i \cup S_j$ cannot contain any cycle and therefore induce a forest. Level 2 is used in Theorem 1(2,4) to bound the global slack ceiling and classify all $9{,}654$ boundary orbits by minimum slack $s_{\min}(G[X])$, and in Theorem 4 at $t = 2, B = 0$ (check_t2_exact42.py, where $9$-vertex-criticality of $G - S$ excludes the $3$ pure $(5, 0, 0)$ multisets because there exist independent triples $S$ and vertices $v \in V(G) \setminus S$ for which $G - S - v$ is not $8$-colorable).

Theorem 1 (Three-Triple Slack Identity, Analytical Ceilings, and Order-$1296$ $G[X]$ Census).

1. (Exact Slack Identity from $\delta(G - S_i) \geq 8$) For each $x \in S_i$ with $\{j, k\} = \{1, 2, 3\} \setminus \{i\}$, $\delta(G - S_j) \geq 8$ and $\delta(G - S_k) \geq 8$ imply $d_G(x) \geq 8 + \max(d_{S_j}(x), d_{S_k}(x))$. Defining the vertex slack $\varepsilon_x = d_G(x) - 8 - \max(d_{S_j}(x), d_{S_k}(x)) \geq 0$ and the tripartite imbalance$$ B_{\triangle} = \frac{1}{2} \sum_{x \in X} |d_{S_j}(x) - d_{S_k}(x)| = \sum_{x \in X} \max(d_{S_j}(x), d_{S_k}(x)) - e(G[X]) \in \mathbb{Z}_{\geq 0}, $$the core edge count $e(C) = |E(C)|$ satisfies the exact identity$$ 42 - e(C) = \eta + \sum_{x \in X} \varepsilon_x + B_{\triangle}. $$
2. (Boundary-Side Slack Ceiling from $9$-Criticality of $G - S_i$) Under the $9$-criticality bound $e(G - S_i) \geq f_9(18) = 76$ ($i \in \{1, 2, 3\}$) [9], each triple satisfies $\sum_{x \in S_i} d_G(x) \leq 38 - \eta$, and summing over $i = 1, 2, 3$ yields$$ 3\eta + \sum_{x \in X} \varepsilon_x + B_{\triangle} \leq 42 - e(G[X]) \leq 33. $$
3. (Core-Side Degree & Slack Ceiling from $\delta(G - S_i) \geq 8$) Every core vertex $u \in V(C)$ satisfies $3 d_C(u) + 2|Y_u| \geq 24$, i.e., $d_C(u) \geq \lceil 8 - \frac{2}{3}|Y_u| \rceil$, and globally $3 e(C) + e(X, C) \geq 144$. When $\chi(C) = 8$ ($K_8 \subseteq C$), $e(C) \geq 32$ ($42 - e(C) \leq 10$) unconditionally, $e(C) \geq 34$ ($42 - e(C) \leq 8$) whenever $|Y_u| \leq 8$ for all $u \in C \setminus K_8$, and $e(C) \geq 36$ ($42 - e(C) \leq 6$) whenever $|Y_u| \leq 7$ for all $u \in C \setminus K_8$.
4. (Exact Order-$1296$ Tripartite $G[X]$ Orbit Classification) Among all $2^{27} = 134{,}217{,}728$ labelled tripartite graphs on $X = S_1 \sqcup S_2 \sqcup S_3$, exactly $11{,}142{,}487$ satisfy $\alpha(G[X]) \leq 3$, partitioning into $9{,}654$ exact orbits under the order-$1296$ group $(S_3)^3 \rtimes S_3$. Across all $9{,}654$ orbits, $B_{\triangle} \in \{0, 1, 2, 3, 4, 5, 6\}$ and the minimum achievable slack $s_{\min}(G[X]) = B_{\triangle} + \min \sum_{x \in X} \varepsilon_x$ (subject to $\delta(G) \geq 9$, $\delta(G - T) \geq 8$ for all independent $X$-triples $T$, pair-graph degree-$8$ Gallai forests in $G - S_k$, and $\sum_{v \in S_i} d_G(v) \leq 38$) lies in $\{0, \ldots, 12\}$.

Proof.

• Part 1: For $x \in S_i$, since $S_j$ is an independent triple not containing $x$, $d_{G - S_j}(x) = d_G(x) - d_{S_j}(x) \geq 8$, and similarly $d_G(x) - d_{S_k}(x) \geq 8$. Using $\max(a, b) = \frac{1}{2}(a + b + |a - b|)$ and $d_X(x) = d_{S_j}(x) + d_{S_k}(x)$, we have$$ d_G(x) = 8 + \frac{1}{2} d_X(x) + \frac{1}{2}|d_{S_j}(x) - d_{S_k}(x)| + \varepsilon_x. $$Summing over all $9$ vertices $x \in X$ and using $\sum_{x \in X} d_X(x) = 2 e(G[X])$ gives$$ \sum_{x \in X} d_G(x) = 72 + e(G[X]) + B_{\triangle} + \sum_{x \in X} \varepsilon_x. $$Since $e(X, C) = \sum_{x \in X} (d_G(x) - d_X(x)) = \sum_{x \in X} d_G(x) - 2 e(G[X]) = 72 - e(G[X]) + B_{\triangle} + \sum_{x \in X} \varepsilon_x$, substituting into $114 - \eta = e(G) = e(G[X]) + e(X, C) + e(C)$ cancels $e(G[X])$ and yields $114 - \eta = 72 + B_{\triangle} + \sum_{x \in X} \varepsilon_x + e(C)$, i.e., $42 - e(C) = \eta + \sum_{x \in X} \varepsilon_x + B_{\triangle}$.
• Part 2: By Kostochka–Yancey [9], any $9$-critical graph on $18$ vertices has at least $\lceil (10 \cdot 7 \cdot 18 - 54)/16 \rceil = 76$ edges. When $G - S_i$ is $9$-critical, $e(G - S_i) \geq 76$. Since $S_i$ is independent, $\sum_{x \in S_i} d_G(x) = e(G) - e(G - S_i) \leq (114 - \eta) - 76 = 38 - \eta$. Summing over $i = 1, 2, 3$ gives $72 + e(G[X]) + B_{\triangle} + \sum_{x \in X} \varepsilon_x = \sum_{x \in X} d_G(x) \leq 114 - 3\eta$, or $3\eta + \sum_{x \in X} \varepsilon_x + B_{\triangle} \leq 42 - e(G[X])$. Since $\alpha(G[X]) \leq 3$ requires $\delta(G[S_a \cup S_b]) \geq 1$, every vertex has $d_X(x) \geq 2$, so $e(G[X]) \geq 9$ and $42 - e(G[X]) \leq 33$.
• Part 3: For each $u \in V(C)$ and $i \in \{1, 2, 3\}$, $d_{G - S_i}(u) = d_C(u) + |Y_u \setminus S_i| \geq 8$. Summing over $i = 1, 2, 3$ and noting that $\sum_{i=1}^3 |Y_u \setminus S_i| = 2|Y_u|$ gives $3 d_C(u) + 2|Y_u| \geq 24$. Summing over all $12$ vertices $u \in V(C)$ gives $6 e(C) + 2 e(X, C) \geq 288$, or $3 e(C) + e(X, C) \geq 144$. When $K_8 \subseteq C$ ($|R_C| = 4$), $e(C) = 28 + e(R_C, K_8) + e(R_C) \geq 28 + \frac{1}{2} \sum_{u \in R_C} d_C(u)$. Since $|Y_u| \leq 9$ gives $d_C(u) \geq \lceil 8 - 18/3 \rceil = 2$, we have $e(C) \geq 28 + 4 = 32$ ($42 - e(C) \leq 10$) unconditionally. When $|Y_u| \leq 8$ for all $u \in R_C$, $d_C(u) \geq \lceil 8 - 16/3 \rceil = 3$ (and $d_C(u) \geq 4$ for $|Y_u| \leq 7$), giving $e(C) \geq 28 + 6 = 34$ ($42 - e(C) \leq 8$, and $\leq 6$ if $|Y_u| \leq 7$).
• Part 4: Every $4$-subset of $X = S_1 \sqcup S_2 \sqcup S_3$ intersects $(S_1, S_2, S_3)$ in sizes $(3, 1, 0)$, $(2, 2, 0)$, or $(2, 1, 1)$. Absence of $(3, 1, 0)$ and $(2, 2, 0)$ independent $4$-sets holds if and only if each $3 \times 3$ bipartite block $M_{ab}$ ($1 \leq a < b \leq 3$) has no zero row, no zero column, and no $2 \times 2$ zero submatrix ($247$ of the $512$ matrices, forming $15$ $S_3 \times S_3$-orbits). Absence of $(2, 1, 1)$ independent $4$-sets holds if and only if every non-edge $(u \in S_a, v \in S_b)$ satisfies $|N_{S_c}(u) \cup N_{S_c}(v)| \geq 2$. Canonicalizing all surviving triples $(M_{12}, M_{13}, M_{23})$ under $(S_3)^3 \rtimes S_3$ (src/enumerate_t18_gx_orbits.py, $3.0\text{ s}$; independently confirmed by low_alpha_designer's $2^{27}$ C scan) yields the exact counts in Table 1. $\square$

| Invariant | Exact Distribution Across the $9{,}654$ Order-$1296$ Orbits of $G[X]$ | |---|---| | Imbalance $B_{\triangle} \in \{0, \ldots, 6\}$ | 0: 18, 1: 182, 2: 1245, 3: 3236, 4: 3415, 5: 1374, 6: 184 | | Minimum slack $s_{\min}(G[X]) \in \{0, \ldots, 12\}$ | 0: 3, 1: 41, 2: 488, 3: 1735, 4: 2639, 5: 2285, 6: 1415, 7: 700, 8: 260, 9: 68, 10: 16, 11: 3, 12: 1 | | Edges $e(G[X]) \in \{9, \ldots, 27\}$ | 9: 1, 10: 1, 11: 9, 12: 35, 13: 151, 14: 463, 15: 1078, 16: 1724, 17: 2034, 18: 1792, 19: 1224, 20: 665, 21: 304, 22: 114, 23: 40, 24: 13, 25: 4, 26: 1, 27: 1 |

Among the $18$ balanced orbits ($B_{\triangle} = 0$), where $d_{S_j}(x) = d_{S_k}(x) \in \{1, 2, 3\}$ for all $x \in X$, the minimum achievable slack $s_{\min}(G[X]) = \min \sum_{x \in X} \varepsilon_x$ partitions the $18$ orbits as follows:

• $s_{\min}(G[X]) = 0$ ($3$ orbits, $t \in \{0, 1, 2\}$): Here $d_X(x) \in \{2, 4\}$ for all $x \in X$, and $G[X]$ consists of three vertex-disjoint primary triangles $Q_1, Q_2, Q_3$ together with $t \in \{0, 1, 2\}$ disjoint transversal triangles ($e(G[X]) = 9 + 3t \in \{9, 12, 15\}$, giving $36 + 216 + 216 = 468$ labelled graphs). These $3$ boundary graphs generate all $3$ orbits at $(\eta, B, B_{\triangle}) = (\eta, 0, 0)$, $5$ of the $8$ orbits at $(\eta, 1, 0)$, and $18$ orbits at $(\eta, 2, 0)$.
• $s_{\min}(G[X]) = 1$ ($2$ orbits, G15_A = (87, 87, 283) and G15_B = (94, 94, 283)): Both have $e(G[X]) = 15$ and contain a $4$-cycle $C_4 \subseteq G[S_2 \cup S_3]$ on $\{3, 4\} \times \{6, 7\}$ (m12 = 283), which violates the Gallai forest condition at $B = 0$ ($\varepsilon = 0$) unless at least one vertex of $\{3, 4, 6, 7\}$ has $\varepsilon_x \geq 1$. In G15_A, vertex $0$ has $d_X(0) = 6, d_G(0) = 11, d_C(0) = 5$. Together, G15_A ($\varepsilon_3 = 1$) and G15_B ($\varepsilon_3 = 1$ and $\varepsilon_4 = 1$) contribute the remaining $3$ order-$1296$ orbits at $(\eta, 1, 0)$, bringing the total at $B = 1$ to $8$ orbits ($8{,}100$ labelled placements over $1{,}440$ graphs).
• $s_{\min}(G[X]) = 2$ ($9$ orbits) and $s_{\min}(G[X]) \geq 3$ ($4$ orbits): Higher-density balanced boundary graphs ($e(G[X]) \in \{15, 18, 21, 24, 27\}$) requiring at least $2$ or $3$ vertex degree bumps to break all bipartite cycles among degree-$8$ vertices of $G - S_k$.

---

4. Color-Class Multiplicity, $(6, 7)$-Core Peeling of $R_C$, and Single-Vertex Kempe Forced-Bit Theory

4.1 The Color-Class Multiplicity Identity (Lemma CCM) and Pair-Incompatibility

Why do naive searches over $12$-element multisets of boundary neighborhoods $(Y_v)_{v \in C}$ stall when $\chi(C) = 7$? Because a proper $7$-coloring $\mathcal{I} = (I_1, \ldots, I_7)$ of $C$ extends to a proper $9$-coloring of $G$ if and only if there exist $7$ boundary independent sets $J_s \subseteq A_s := \bigcap_{v \in I_s} M_X(v)$ whose removal leaves $G[X \setminus \bigcup_{s=1}^7 J_s]$ bipartite ($2$-colorable with colors $\{8, 9\}$).

Lemma 1 (Color-Class Multiplicity Identity — Lemma CCM). Let $\mathcal{I} = (I_1, \ldots, I_k)$ be a partition of $V(C)$ into $k$ color classes, and for each $x \in X$ let $A_s = \{x \in X : N_G(x) \cap I_s = \emptyset\}$ and $c(x) = |\{s \in \{1, \ldots, k\} : x \in A_s\}|$. Then for every $x \in X$:

$$ \sum_{s \,:\, x \notin A_s} \bigl(|N_{I_s}(x)| - 1\bigr) = c(x) - \bigl(k - d_C(x)\bigr). $$

In particular, for $k = 7$:

1. If $x \in \operatorname{deg7\_X} := \{x \in X : d_C(x) = 7\}$, then $\sum_{s : x \notin A_s} (|N_{I_s}(x)| - 1) = c(x)$. Thus $c(x) = 0$ if and only if $|N_{I_s}(x)| = 1$ for all $s \in \{1, \ldots, 7\}$; equivalently, whenever two vertices $u, v \in I_s$ in the same color class both see $x \in \operatorname{deg7\_X}$, we have $|N_{I_s}(x)| \geq 2$ and hence $c(x) \geq 1$.
2. If $x \in \operatorname{deg8\_X} := \{x \in X : d_C(x) = 8\}$, then $\sum_{s : x \notin A_s} (|N_{I_s}(x)| - 1) = c(x) + 1$. Whenever three vertices $u, v, w \in I_s$ in a size-$3$ color class all see $x \in \operatorname{deg8\_X}$, we have $|N_{I_s}(x)| - 1 = 2$, forcing $c(x) \geq 1$.
3. If $x \in \operatorname{deg6\_X} := \{x \in X : d_C(x) \leq 6\}$, then $c(x) \geq 7 - d_C(x) \geq 1$ unconditionally.

Proof. Partitioning the $d_C(x)$ neighbors of $x$ in $C$ across the $k - c(x)$ color classes $I_s$ for which $x \notin A_s$ gives $\sum_{s : x \notin A_s} |N_{I_s}(x)| = d_C(x)$. Subtracting $\sum_{s : x \notin A_s} 1 = k - c(x)$ from both sides yields $\sum_{s : x \notin A_s} (|N_{I_s}(x)| - 1) = d_C(x) - k + c(x) = c(x) - (k - d_C(x))$. $\square$

We pair Lemma 1 with the Non-Adjacent Degree-$9$ Pair Clique Theorem: if a core vertex $v \in C$ is adjacent to two non-adjacent boundary vertices $a, b \in X$ both having $d_G(a) = d_G(b) = 9$, then no independent triple $S$ of $G$ can contain $v$ (otherwise $S \cup \{a\}$ or $S \cup \{b\}$ would be independent of size $4$, or deleting $S$ would drop $d_{G-S}(a)$ or $d_{G-S}(b)$ below $8$). Since $\alpha(G) = 3$, the non-neighborhood $M_G(v) = M_C(v) \cup M_X(v)$ of any such $v$ must be a clique in $G$, forcing $d_G(v) = 20 - |M_G(v)| \geq 20 - \omega(G) \geq 12$ ($d_C(v) \geq 12 - |Y_v|$), $|M_C(v)| \leq \omega(C)$, and $Y_v \cup Y_w = X$ for every $w \in M_C(v)$.

4.2 Unused Clique-Color Pigeonhole Bound, $(6, 7)$-Core Peeling of $R_C$, and Kempe Forced-Bit Pruning

When $\chi(C) = 7$ and $K_7 \subseteq C$, we write $C = K_7 \sqcup R_C$ with $|R_C| = 5$. For each $i \in \{0, \ldots, 4\}$ in $R_C$, let $b_i = |N_{K_7}(i)|$ be the number of cross-edges to $K_7$, encoded by the $7$-bit mask $m_i \in \{0, \ldots, 127\}$ ($\operatorname{popcount}(m_i) = b_i$).

Theorem 2 (Pigeonhole Unused-Color Bound on $R_C$, Cascade Peeling at $T \in \{6, 7\}$, and Kempe Forced-Bit Theorem).

1. (Unconditional Pigeonhole Bound on $W = R_C$ and Threshold-$6$ Peeling) In any proper $7$-coloring $c$ of $C = K_7 \sqcup R_C$, because $|R_C| = 5$, the color set $c(R_C) \subseteq \{0, \ldots, 6\}$ has size $|c(R_C)| \leq 5$, so the set of unused $K_7$-colors $A = \{0, \ldots, 6\} \setminus c(R_C)$ satisfies $|A| \geq 7 - 5 = 2$ unconditionally by the Pigeonhole Principle, and every $q \in \bigcap_{i=0}^4 \operatorname{eff\_forced}[i]$ belongs to $A$. Furthermore, if peeling $R_C$ at degeneracy threshold $T_1 = 6$ (retaining $i \in W$ while $b_i + d_{R_C[W]}(i) \geq 6$) leaves a non-empty subcore $W_6 \subseteq R_C$, then in at least one proper $7$-coloring of $C[K_7 \cup W_6]$ the color set $A_6 = \{0, \ldots, 6\} \setminus c(W_6)$ satisfies $|A_6| \geq 1$ with $\bigcap_{i \in W_6} \operatorname{eff\_forced}[i] \subseteq A_6$.
2. (Pair-Incompatibility Cascade Forcing at $T \in \{6, 7\}$) Let $\operatorname{h3\_mask}[i] \subseteq \{0, \ldots, 6\}$ denote the set of $q \in K_7$ such that $\{i, q\}$ cannot share color $q$ in any non-extending $7$-coloring (because $M_X(i) \cap M_X(q)$ extends at size $1$, or $(Y_i \cap Y_q \cap \operatorname{deg7\_X}) \cup \operatorname{deg6\_X}$ contains an independent odd-cycle transversal of $G[X]$ by Lemma 1). If peeling $R_C \setminus \{i\}$ at threshold $T = 7$ (or $T = 6$ for $R_C$-neighbors of $i$ not forced to see $q$) leaves no unforced $R_C$-neighbor of $i$ available to take color $q$, then the cross-edge $(i, q) \in E(R_C, K_7)$ is forced ($\operatorname{eff\_forced}[i] \gets \operatorname{eff\_forced}[i] \cup \{q\}$).
3. (Single-Vertex Kempe Re-Coloring & Forced-Bit Theorem) Let $\operatorname{bad\_cols}(R_C)$ be the set of proper $7$-colorings $\operatorname{col} = (c_0, \ldots, c_4) \in \{0, \ldots, 6\}^5$ of $R_C$ that respect $\operatorname{eff\_forced}$, satisfy $\alpha(G) = 3$ and $\delta(G - S) \geq 8$ on every color class $I_q$, and fail to extend to a $9$-coloring of $G$. For any $\operatorname{col} \in \operatorname{bad\_cols}(R_C)$ and any $i \in \{0, \ldots, 4\}$, every color $q \in \{0, \ldots, 6\} \setminus (\{c_i\} \cup \{c_j : ij \in E(R_C)\})$ whose single-vertex re-coloring $\operatorname{col}^{(i \to q)} = (c_0, \ldots, q, \ldots, c_4)$ is not in $\operatorname{bad\_cols}(R_C)$ must be blocked by the cross-edge $(i, q) \in E(R_C, K_7)$, forcing bit $q$ of $m_i$ to be $1$:$$ \operatorname{req\_m}[i](\operatorname{col}) = \operatorname{eff\_forced}[i] \;\Big|\; \bigcup_{\substack{q \neq c_i,\, q \notin c(N_{R_C}(i)) \\ \operatorname{col}^{(i \to q)} \notin \operatorname{bad\_cols}(R_C)}} \{q\}, \qquad (m_i \mathbin{\&} \operatorname{req\_m}[i](\operatorname{col})) = \operatorname{req\_m}[i](\operatorname{col}). $$

Proof.

• Part 1: Since $|R_C| = 5$, any map $c : R_C \to \{0, \ldots, 6\}$ has image size $|c(R_C)| \leq 5$, so $A = \{0, \ldots, 6\} \setminus c(R_C)$ has size $|A| = 7 - |c(R_C)| \geq 2$. For any $q \in \bigcap_{i=0}^4 \operatorname{eff\_forced}[i]$, every $i \in R_C$ is adjacent to $q \in K_7$, so $c(i) \neq q$ in any proper $7$-coloring of $C$; hence $\bigcap_{i=0}^4 \operatorname{eff\_forced}[i] \subseteq A$. Thus if every subset $A \subseteq \{0, \ldots, 6\}$ of size $\geq 2$ containing $\text{fm} = \bigcap_{i=0}^4 \operatorname{eff\_forced}[i]$ contains a $1$-class or $2$-class boundary extension (min_w2[fm] > 5 or min_w3[fm] > 5), every proper $7$-coloring of $C$ extends to $G$. Similarly, any vertex $i \in R_C \setminus W_6$ peeled at threshold $T_1 = 6$ has $< 6$ neighbors in $K_7 \cup W_6$ at the moment of removal, so any proper $7$-coloring of $K_7 \cup W_6$ extends greedily to $C$.
• Part 2: Suppose $(i, q) \notin E(R_C, K_7)$ and $q \in \operatorname{h3\_mask}[i]$. To prevent $C$ from admitting a $7$-coloring in which $i$ and $q$ share color $q$, any greedy $7$-coloring of $C$ starting from $K_7$ must be blocked from assigning color $q$ to $i$ by some $R_C$-neighbor $j \in N_{R_C}(i)$ receiving color $q$. Any vertex $z \in R_C \setminus \{i\}$ with degree $< 7$ in $C[K_7 \cup S]$ (or $< 6$ if $z \in N_{R_C}(i)$ and $z \sim q$ is not forced) can always be colored last after its neighbors without using color $q$, so $j$ must survive inside the peeled $(6, 7)$-core $S_q \subseteq R_C \setminus \{i\}$. If no such $j$ exists in $S_q$, $(i, q) \in E(R_C, K_7)$ is forced.
• Part 3: Suppose $(R_C, m_0, \ldots, m_4)$ is a valid core $C = K_7 \cup R_C$ with $\chi(C) = 7$ that admits at least one valid $7$-coloring $\operatorname{col}$ and has no extending $7$-coloring. Then $\operatorname{col} \in \operatorname{bad\_cols}(R_C)$ with $(m_i \gg c_i) \mathbin{\&} 1 = 0$ for all $i$. If for some $i \in \{0, \ldots, 4\}$ and $q \notin \{c_i\} \cup \{c_j : ij \in E(R_C)\}$ we had $\operatorname{col}^{(i \to q)} \notin \operatorname{bad\_cols}(R_C)$ and $(m_i \gg q) \mathbin{\&} 1 = 0$, then $\operatorname{col}^{(i \to q)}$ would be a proper $7$-coloring of $C$ that either violates $\alpha(G) = 3 / \delta(G - S) \geq 8$ (impossible if $G$ is valid) or extends to a $9$-coloring of $G$ (contradicting that no $7$-coloring of $C$ extends). Hence $(m_i \gg q) \mathbin{\&} 1 = 1$ is forced. $\square$

---

5. The Two-Part $K_7$-Free Core Closure Theorem Across All $e(C) \leq 42$ ($\chi(C) = 7, \omega(C) \leq 6$)

We now resolve the $K_7$-free subbranch ($\chi(C) = 7, \omega(C) \leq 6$) across all $B \geq 0$ ($e(C) \leq 42$). Any $12$-vertex graph $C$ with $\chi(C) = 7$ and $\omega(C) \leq 6$ contains a $7$-vertex-critical subgraph $Q \subseteq C$ of order $r_Q = |V(Q)| \leq 12$. Because $\omega(Q) \leq \omega(C) \leq 6$, $Q$ cannot have order $7$ ($K_7$) or $8$ (no $7$-critical graph on $8$ vertices exists), so $r_Q \in \{9, 10, 11, 12\}$. We treat $r_Q = 12$ (where $C$ itself is $7$-critical on $12$ vertices, so $\delta(C) \geq 6$) in Part A, and proper $7$-critical subgraphs $r_Q \in \{9, 10, 11\}$ in Part B.

Theorem 3 (Two-Part $K_7$-Free Core Closure Theorem Across All $e(C) \leq 42$).

1. (Part A — $r_Q = 12$, where $C$ is $7$-vertex-critical on $12$ vertices so $\delta(C) \geq 6 \iff \Delta(\overline{C}) \leq 5$, across all $e(C) \leq 42 \iff e(\overline{C}) \geq 24$) Let $C$ be a $12$-vertex $7$-vertex-critical graph with $\omega(C) \leq 6$, $\alpha(C) \leq 3$, $\delta(C) \geq 6$, and $e(C) \leq 42$, and let $H = \overline{C}$ ($|V(H)| = 12, \alpha(H) \leq 6, \omega(H) \leq 3, \Delta(H) \leq 5, e(H) \geq 24$):
   • (a) When $\alpha(C) = 3$ ($\omega(H) = 3$): No $12$-vertex graph $C$ (critical or not) with $\chi(C) \geq 7$, $\omega(C) \leq 6$, $\alpha(C) = 3$, $\delta(C) \geq 6$, and $e(C) \leq 42$ exists. Consequently, independent of $G[X]$ and $E(X, C)$, no $12$-vertex $7$-critical $K_7$-free core $C$ with $\alpha(C) = 3$ exists at any slack level $42 - e(C) = \eta + \sum_{x \in X} \varepsilon_x + B_{\triangle} \geq 0$.
   • (b) When $\alpha(C) \leq 2$ ($H$ is triangle-free, $\omega(H) \leq 2$): Every such $12$-vertex $7$-vertex-critical graph $C$ with $e(C) \leq 42$ has $\alpha(C) = 2$ and is a single-apex join $C \cong \{v_0\} \vee \overline{C_1^{(g)}}$ ($d_C(v_0) = 11$, so $H = C_1^{(g)} \sqcup \{v_0\}$), where $C_1^{(g)}$ ($g \in \{1, \ldots, 28\}$) is one of exactly $28$ non-isomorphic $11$-vertex factor-critical triangle-free graphs ($\nu(C_1^{(g)} - w) = 5$ for all $w \in V(C_1^{(g)})$) with $\alpha(C_1^{(g)}) = 5$, $\Delta(C_1^{(g)}) = 5$, $\nu(C_1^{(g)}) = 5$, and $e(C_1^{(g)}) \in \{24, 25, 26\}$ ($20$ graphs with $e(C_1) = 24, e(C) = 42$; $6$ graphs with $e(C_1) = 25, e(C) = 41$; and $2$ graphs with $e(C_1) = 26, e(C) = 40$). Across all $29$ balanced boundary-slack orbits ($B \in \{0, 1, 2\}, \eta \geq 0$) and all $39$ first-slack unbalanced (0, 0, 1) orbits ($e(C) \leq 41$), these single-apex cores yield 0 survivors (tf_surv = 0).
2. (Part B — $r_Q \in \{9, 10, 11\}$, where $C$ contains a proper $7$-critical subgraph $Q \subsetneq C$) Let $d_{(1)} \leq d_{(2)} \leq \cdots \leq d_{(12)}$ be the sorted vertex degrees of $C$. By Gallai's theorem [10] ($r_Q \leq 12 = 2(7) - 2$), any $7$-critical $K_7$-free subgraph $Q \subsetneq C$ of order $r_Q \in \{9, 10, 11\}$ is a join, forcing:
   • for $r_Q = 9$: $Q \cong K_4 \vee C_5$ ($e(Q) = 31$), so $e(C) \geq 28 + d_{(1)} + d_{(2)} + d_{(3)}$;
   • for $r_Q = 10$: $Q \cong K_3 \vee H_7$ ($e(Q) \geq 35$), so $e(C) \geq 34 + d_{(1)} + d_{(2)}$;
   • for $r_Q = 11$: $Q \in \{K_4 \vee C_7,\, K_3 \vee H_8,\, K_2 \vee H_9,\, C_5 \vee H_6\}$ ($e(Q) \geq 38$), so $e(C) \geq 38 + d_{(1)}$. Whenever $\delta(C) \geq 5$, all three bounds give $e(C) \geq \min(28 + 15,\, 34 + 10,\, 38 + 5) = 43 > 42 - B$. Moreover, for any unextendable $7$-partition $\mathcal{P} = \{P_1, \ldots, P_7\}$ of $V(C)$ in $\mathcal{P}_{\text{bad}}$, every singleton class $P_s = \{u\}$ satisfies $d_C(u) \geq 6$, and every vertex $u \in P_s$ ($|P_s| \geq 2$) satisfies $d_C(u) \geq |\{t \neq s : \mathcal{P}^{(u \to t)} \notin \mathcal{P}_{\text{bad}}\}|$. Across all $29$ balanced orbits ($B \in \{0, 1, 2\}, \eta \geq 0$) and all $39$ first-slack unbalanced (0, 0, 1) orbits ($e(C) \leq 41$), combining these bounds with forced core degrees and the $K_4 \vee C_5$ Five-Partition Extension Filter yields 0 surviving multisets for $r_Q \in \{9, 10, 11\}$.

Proof.

• Part A ($r_Q = 12$): Let $H = \overline{C}$ have $|V(H)| = 12$, $\alpha(H) = \omega(C) \leq 6$, $\omega(H) = \alpha(C) \leq 3$, $\Delta(H) = 11 - \delta(C) \leq 5$, and $e(H) = 66 - e(C) \geq 24$, with $\chi(C) \geq 7$ (so $V(H)$ cannot be covered by $6$ cliques of $H$).
  • Step A1 (Triangle-Free Complement Subcase $\omega(H) \leq 2 \iff \alpha(C) \leq 2$: Tutte–Berge Formula and Exact $28$-Graph Factor-Critical Classification): Suppose $H$ is triangle-free ($\omega(H) \leq 2$). Then every clique of $H$ is a vertex or an edge, so $\chi(C) = 12 - \nu(H)$, where $\nu(H)$ is the matching number of $H$. Thus $\chi(C) \geq 7$ if and only if $\nu(H) \leq 5$ (for example, $H = K_{6,6} - M$ has $e(H) = 30$ and $\alpha(H) = 6$, but $\nu(H) = 6$, so $\chi(\overline{H}) = 6$). By the Tutte–Berge Formula, $\nu(H) = \frac{1}{2}\min_{U \subseteq V(H)}(|V(H)| + |U| - o(H - U)) \leq 5$ if and only if there exists $U \subseteq V(H)$ of size $u = |U|$ such that $H - U = R_{\text{even}} \sqcup C_1 \sqcup \cdots \sqcup C_q$ has an even-order union of even components $R_{\text{even}}$ of order $r_{\text{even}} \in \{0, 2, 4, 6, 8, 10\}$ and $q = o(H - U) \geq u + 2$ odd connected components $C_1, \ldots, C_q$ of odd orders $c_1 \geq \cdots \geq c_q \geq 1$ ($\sum_{i=1}^q c_i = 12 - u - r_{\text{even}}$, with $q - u \equiv 12 \pmod 2$) and independence numbers $\alpha_i = \alpha(C_i) \geq 1$. Since $R_{\text{even}}, C_1, \ldots, C_q$ are pairwise disjoint induced subgraphs of $H - U$, we have $\alpha(R_{\text{even}}) + \sum_{i=1}^q \alpha_i = \alpha(H - U) \leq \alpha(H) \leq 6$. In any triangle-free graph $F$ of order $n$ and independence number $\alpha$, every neighborhood $N_F(v)$ is independent so $\Delta(F) \leq \alpha$, giving $e(F) \leq g(n, \alpha) := \min(\lfloor n\alpha / 2 \rfloor, \lfloor n^2 / 4 \rfloor)$ (and exact maxima $f(n, \alpha)$: $f(1,1)=f(3,1)=0, f(3,2)=2, f(5,2)=5, f(5,3)=6, f(7,3)=10, f(7,4)=12, f(9,4)=17, f(9,5)=20, f(11,4)=22, f(11,5)=26$). Moreover, for the even triangle-free remainder $R_{\text{even}}$ of order $r_{\text{even}}$, Mantel's theorem gives $e(R_{\text{even}}) \leq \lfloor r_{\text{even}}^2 / 4 \rfloor$, and Ramsey's theorem ($R(3, 2) = 3, R(3, 3) = 6$) gives $\alpha(R_{\text{even}}) \geq 1$ for $r_{\text{even}} = 2$, $\alpha(R_{\text{even}}) \geq 2$ for $r_{\text{even}} = 4$, and $\alpha(R_{\text{even}}) \geq 3$ for $r_{\text{even}} \in \{6, 8\}$. Since $\Delta(H) \leq 5$, all edges incident to $U$ (both inside $U$ and between $U$ and $H - U$) total at most $5u$, so $e(H) \leq 5u + \lfloor r_{\text{even}}^2 / 4 \rfloor + \sum_{i=1}^q f(c_i, \alpha_i)$:
    1. When $u = 0$ ($U = \emptyset$): $H = R_{\text{even}} \sqcup C_1 \sqcup \cdots \sqcup C_q$, so in the complement $C = \overline{H} = \overline{R_{\text{even}}} \vee \overline{C_1} \vee \cdots \vee \overline{C_q}$ is a complete join. For each odd component $C_i$, $\alpha(\overline{C_i}) \leq 2$ implies $\chi(\overline{C_i}) \geq \lceil c_i / 2 \rceil = (c_i + 1)/2$. Furthermore, if $r_{\text{even}} \geq 2$, then for any vertex $v \in V(R_{\text{even}})$, the subgraph $\overline{R_{\text{even}}} - v$ has $r_{\text{even}} - 1$ vertices and $\alpha \leq 2$, so $\chi(\overline{R_{\text{even}}} - v) \geq \lceil (r_{\text{even}} - 1)/2 \rceil = r_{\text{even}}/2$; by $7$-vertex-criticality of $C$, $\overline{R_{\text{even}}}$ is vertex-critical, so $\chi(\overline{R_{\text{even}}}) = \chi(\overline{R_{\text{even}}} - v) + 1 \geq r_{\text{even}}/2 + 1$. Summing chromatic numbers across the join gives$$ 7 = \chi(C) = \chi(\overline{R_{\text{even}}}) + \sum_{i=1}^q \chi(\overline{C_i}) \geq \mathbf{1}_{r_{\text{even}} \geq 2} + \frac{r_{\text{even}} + \sum_{i=1}^q c_i + q}{2} = \mathbf{1}_{r_{\text{even}} \geq 2} + 6 + \frac{q}{2}, $$which uniquely forces $r_{\text{even}} = 0$ and $q = 2$ at $u = 0$. If $c_1 \leq 9$, then $(c_1, c_2) \in \{(9, 3), (7, 5)\}$, giving $e(H) \leq \max(f(9, 4) + f(3, 2),\, f(9, 5) + f(3, 1),\, f(7, 3) + f(5, 3)) = \max(17 + 2,\, 20 + 0,\, 10 + 6) = 20 < 24$. If $(c_1, c_2) = (11, 1)$ and $\alpha_1 \leq 4$, then $e(H) \leq f(11, 4) + 0 = 22 < 24$.
    2. When $u \geq 1$: evaluating $5u + \lfloor r_{\text{even}}^2 / 4 \rfloor + \sum_{i=1}^q f(c_i, \alpha_i)$ across all $u \in \{1, \ldots, 5\}$, all $r_{\text{even}} \in \{0, 2, 4, 6, 8\}$, all $q \geq u + 2$, and all odd partitions with $\sum_{i=1}^q \alpha_i \leq 6 - \alpha_{\min}(R_{\text{even}})$ (verify_triangle_free_complement_classification() in src/check_k7free_all_B.py) gives $\max e(H) = 22 < 24$ (attained at $u = 1, r_{\text{even}} = 0, q = 3, (c_1, c_2, c_3) = (9, 1, 1), (\alpha_1, \alpha_2, \alpha_3) = (4, 1, 1)$, where $5 + 17 = 22$). Therefore, $e(H) \geq 24$ uniquely forces $u = 0$, $r_{\text{even}} = 0$, $q = 2$, $(c_1, c_2) = (11, 1)$, and $(\alpha_1, \alpha_2) = (5, 1)$: $H = C_1 \sqcup \{v_0\}$ where $v_0$ is an isolated vertex of $H$ ($d_C(v_0) = 11$, so $C = \{v_0\} \vee \overline{C_1}$ has a universal apex $v_0$ and $\alpha(C) = 2$), and $C_1$ is an $11$-vertex triangle-free graph with $\alpha(C_1) = 5$, $\Delta(C_1) \leq 5$, $\nu(C_1) = 5$, and $e(C_1) = e(H) \in \{24, 25, 26\}$. Crucially, because $C = \{v_0\} \vee \overline{C_1}$, $C$ is $7$-vertex-critical if and only if $\overline{C_1}$ is $6$-vertex-critical; since $\chi(\overline{C_1} - w) = 10 - \nu(C_1 - w)$, $\overline{C_1}$ is $6$-vertex-critical if and only if $\nu(C_1 - w) = 5$ for every $w \in V(C_1)$, i.e., $C_1$ is factor-critical. Let $I = \{0, \ldots, 4\}$ be a $5$-independent set of $C_1$ and $R = C_1 - I = \{5, \ldots, 10\}$ ($|V(R)| = 6$). Since $\Delta(C_1) \leq 5$, $e_{C_1}(I, R) \leq 25$ and $e_{C_1}(I, R) + 2e(R) \leq 30$. Subtracting $e_{C_1}(I, R) + e(R) = e(C_1) \geq 24$ gives $1 \leq e(R) \leq 30 - e(C_1) \leq 6$ and $e_{C_1}(I, R) \geq 24 - e(R) \geq 18$. Exhaustive enumeration of all $6$-vertex triangle-free graphs $R$ with $1 \leq e(R) \leq 6$ and all $S_5$-canonical neighborhood assignments $(N_I(v))_{v \in V(R)}$ satisfying $\Delta(C_1) \leq 5$, triangle-freeness, and $\alpha(C_1) = 5$ (verify_triangle_free_complement_classification() in src/check_k7free_all_B.py, $9.5\text{ s}$) yields $389$ $S_5$-canonical realizations with $e(C_1) \geq 24$ (including $63$ with $e(C_1) \geq 25$), which collapse under isomorphism to $28$ non-isomorphic $11$-vertex factor-critical triangle-free graphs $C_1^{(1)}, \ldots, C_1^{(28)}$ (RAW_28_GRAPHS in src/check_k7free_all_B.py: $20$ graphs with $e(C_1) = 24, e(C) = 42$; $6$ graphs with $e(C_1) = 25, e(C) = 41$; and $2$ graphs with $e(C_1) = 26, e(C) = 40$). In $27$ of the $28$ graphs, $V(C_1^{(g)}) = \{v_5\} \sqcup I \sqcup J$ partitions into two disjoint $5$-independent sets $I, J$ and a vertex $v_5$ (while the $28$th graph has $\delta(C_1^{(28)}) = 4 \iff \Delta(\overline{C_1^{(28)}}) = 6$, so every vertex $u \in V(C_1^{(28)})$ has $d_C(u) \in \{6, 7\}$), and by factor-criticality every vertex $w \in V(C_1^{(g)})$ is left uncovered by a non-empty family of $5$-matchings $M$ of $C_1^{(g)} - w$. Running check_tf_8graphs_on_sols() in src/check_k7free_all_B.py across all $28$ graphs at $B = 0$ ($e(C_1) \geq 24$), the $8$ graphs at $B = 1$ ($e(C_1) \geq 25$), and the $2$ graphs at $B = 2$ ($e(C_1) = 26$) across all $29$ balanced orbits confirms 0 survivors (tf_surv = 0).
  • Step A2 ($\omega(H) = 3$: $H$ Contains a Triangle $T$, and $Q_9 = C - T$ Contains $K_6$): Now suppose $\alpha(C) = 3$, so $H$ contains a triangle $T = \{w_0, w_1, w_2\}$. Removing $T$ from $C$ leaves a $9$-vertex graph $Q_9 = C - T$ with $\chi(Q_9) \geq \chi(C) - 1 \geq 6$ and $\omega(Q_9) \leq 6$. Suppose for contradiction that $\omega(Q_9) \leq 5$. Then $Q_9$ contains a $6$-critical subgraph $R \subseteq Q_9$ of order $r_R \in \{8, 9\}$ (since $\omega(R) \leq 5$ rules out $K_6$, and no $6$-critical graph on $7$ vertices exists). By Gallai's theorem [10] ($r_R \leq 9 < 2(6) - 2 = 10$), $R$ is a join $R_1 \vee R_2$ with $\chi(R_1) + \chi(R_2) = 6$:
    1. If $r_R = 8$, then $R \cong K_3 \vee C_5$ with $e(R) = 3 + 15 + 5 = 23$, so $e(H[R]) = \binom{8}{2} - 23 = 5$, and the $9$th vertex of $Q_9$ has $H$-degree $\leq \Delta(H) \leq 5$, giving $e(H[Q_9]) \leq 5 + 5 = 10$.
    2. If $r_R = 9$, then $R \cong K_2 \vee B_7$ where $B_7$ is a $4$-critical graph on $7$ vertices (note that $K_2 \vee C_7$ has $\chi = 5$, not $6$, and no $5$-critical graph on $6$ vertices exists). By Kostochka–Yancey [9], $e(B_7) \geq 11$, so $e(R) = 1 + 14 + e(B_7) \geq 26$ and $e(H[Q_9]) = \binom{9}{2} - e(Q_9) \leq 36 - 26 = 10$. In both cases, since $\Delta(H) \leq 5$ implies $d_{H, Q_9}(w) \leq 5 - 2 = 3$ for each $w \in T$, we obtain $e(H) = e(H[T]) + e_H(T, Q_9) + e(H[Q_9]) \leq 3 + 9 + 10 = 22 < 24$, a contradiction.
  • Step A3 (Exact Decomposition on $V(H) = T \sqcup K_6 \sqcup S$ and $S_6$-Reduced Exhaustive Verification Across $e(H) \geq 24$): Thus $Q_9$ contains a $6$-clique $K_6 = \{0, \ldots, 5\}$ of $C$ ($e(H[K_6]) = 0$), and $V(H) = T \sqcup K_6 \sqcup S$ where $T = \{w_0, w_1, w_2\}$ ($e(H[T]) = 3$) and $S = \{s_0, s_1, s_2\}$ ($|S| = 3$). Because $\omega(C) \leq 6$, every vertex $v \in T \cup S$ must have at least one $H$-neighbor in $K_6$ ($d_{H, K_6}(v) \geq 1$), and because $\Delta(H) \leq 5$, we have $d_{H, K_6}(w) \leq 3 - d_{H, S}(w)$ for $w \in T$, $d_{H, K_6}(s) \leq 5 - d_{H, T \cup S}(s)$ for $s \in S$, and $d_H(k) \leq 5$ for all $k \in K_6$. Summing over $T \cup S$ gives the exact deficit identity $\sum_{v \in T \cup S} (5 - d_H(v)) + e_H(T, S) + e(H[S]) = 27 - e(H) \leq 3$. Fixing $t_0 = (1 \ll d_{t_0}) - 1$ and canonicalizing $t_1$ under $S_{d_{t_0}} \times S_{6 - d_{t_0}}$, src/check_k7free_all_B.py (24.7\text{ s}) tests all $100{,}725{,}263$ $S_6$-reduced configurations (representing $9{,}200{,}913{,}350$ labelled configurations, including the $11{,}094{,}069$ $S_6$-reduced / $1{,}075{,}714{,}680$ labelled configurations with $e(H) \geq 25$) and confirms that $100\%$ extend the $6$-coloring of $K_6$ to $T \cup S$ (0 non-$6$-colorable realizations).
• Part B ($r_Q \in \{9, 10, 11\}$): Notice that while abstract disconnected or low-degree $12$-vertex graphs containing $K_4 \vee C_5$ exist when boundary coupling is ignored (for example, $(K_4 \vee C_5) \sqcup K_3$ has $\delta(C) = 2, e(C) = 34$, and joining $K_3$ to $2$ vertices of $K_4$ gives $\delta(C) = 4, e(C) = 40$), in $G = X \cup C$ every core vertex $v \in V(C)$ obeys the boundary degree and coloring constraints. Specifically, for $r_Q = 12 - k$ ($k = |V(C) \setminus V(Q)| \in \{1, 2, 3\}$), write $R_k = V(C) \setminus V(Q)$. Since $R_k$ has at most $\binom{k}{2}$ internal edges, $e(C) = e(Q) + \sum_{u \in R_k} d_C(u) - e(C[R_k]) \geq e(Q) - \binom{k}{2} + \sum_{i=1}^k d_{(i)}$. By Gallai's theorem [10], any $7$-critical graph $Q$ of order $r_Q \leq 11 < 2(7) - 2$ is a join $Q_1 \vee Q_2$ with $\chi(Q_1) + \chi(Q_2) = 7$:
  • For $r_Q = 9$ ($k = 3, \binom{3}{2} = 3$): since $\omega(Q) \leq 6$ and the smallest $c$-critical graph not a clique is $C_5$ ($c = 3, n = 5$), $Q = K_4 \vee C_5$ with $e(Q) = 6 + 20 + 5 = 31$, giving $e(C) \geq 31 - 3 + d_{(1)} + d_{(2)} + d_{(3)} = 28 + d_{(1)} + d_{(2)} + d_{(3)}$.
  • For $r_Q = 10$ ($k = 2, \binom{2}{2} = 1$): $Q = K_3 \vee H_7$ where $H_7$ is $4$-critical on $7$ vertices ($e(H_7) \geq 11$ by Kostochka–Yancey [9], so $e(Q) \geq 3 + 21 + 11 = 35$; note that $C_5 \vee C_5$ has $\chi = 6$, not $7$), giving $e(C) \geq 35 - 1 + d_{(1)} + d_{(2)} = 34 + d_{(1)} + d_{(2)}$.
  • For $r_Q = 11$ ($k = 1, \binom{1}{2} = 0$): $Q \in \{K_4 \vee C_7,\, K_3 \vee H_8,\, K_2 \vee H_9,\, C_5 \vee H_6\}$ where $e(K_4 \vee C_7) = 6 + 28 + 7 = 41$, $e(K_3 \vee H_8) \geq 3 + 24 + 12 = 39$, $e(K_2 \vee H_9) \geq 1 + 18 + 19 = 38$, and $e(C_5 \vee H_6) = 5 + 30 + 9 = 44$, so $e(Q) \geq 38$ and $e(C) \geq 38 + d_{(1)}$. Furthermore, if $c : V(C) \to \{1, \ldots, 7\}$ is any proper $7$-coloring of $C$ with color classes $\mathcal{P} = \{P_1, \ldots, P_7\} \in \mathcal{P}_{\text{bad}}$ (failing to extend to $G$):
  1. If $P_s = \{u\}$ is a singleton color class, then $u$ must have at least one neighbor in $C$ in each of the other $6$ color classes $P_t$ ($t \neq s$); otherwise re-coloring $u$ into a color $t$ absent from $N_C(u)$ eliminates color $s$ altogether and produces a proper $6$-coloring of $C$, contradicting $\chi(C) = 7$! Thus $d_C(u) \geq 6$ for every singleton class $P_s = \{u\}$.
  2. If $|P_s| \geq 2$ and $u \in P_s$, then for each $t \neq s$ such that moving $u$ to $P_t$ yields a partition $\mathcal{P}^{(u \to t)} \notin \mathcal{P}_{\text{bad}}$, $u$ must be adjacent in $C$ to at least one vertex of $P_t$ (otherwise $\mathcal{P}^{(u \to t)}$ would be a proper $7$-coloring of $C$ that extends to a $9$-coloring of $G$).
  3. At $r_Q = 9$ ($Q = K_4 \vee C_5 = A_4 \vee W_5$, where $A_4 = \{a_0, a_1, a_2, a_3\}$ is a $4$-clique and $W_5 = (w_0, w_1, w_2, w_3, w_4)$ is ordered along the complement $5$-cycle $\overline{C_5}$ so that consecutive pairs $\{w_{k+1}, w_{k+2}\}$ and $\{w_{k+3}, w_{k+4}\}$ are non-edges of $Q$, i.e., independent sets of $C_5$), $Q$ admits five canonical $7$-colorings $\mathcal{P}_k(Q) = \{\{a_0\}, \{a_1\}, \{a_2\}, \{a_3\}, \{w_k\}, \{w_{k+1}, w_{k+2}\}, \{w_{k+3}, w_{k+4}\}\}$ ($k \in \mathbb{Z}_5$). For $C = Q \sqcup R_3$ ($R_3 = \{u_0, u_1, u_2\}$) to satisfy $\omega(C) \leq 6$ and have no extending $7$-coloring, for each $k \in \mathbb{Z}_5$ at least one placement $(j_0, j_1, j_2) \in \{0, \ldots, 6\}^3$ of $R_3$ into $\mathcal{P}_k(Q)$ must lie in $\mathcal{P}_{\text{bad}}$, and each $u_r \in R_3$ must have a $Q$-neighbor in every class $j \notin \operatorname{Bad}_k(u_r)$ while satisfying $\omega(Q[N_Q(u_r)]) \leq 5$ (valid_k4c5_with_r3()). Running verify_proper_7critical_subgraphs_rQ_9_10_11() in src/check_k7free_all_B.py across all $29$ balanced orbits and src/check_001_k7free.py across all $39$ first-slack unbalanced (0, 0, 1) orbits confirms 0 surviving multisets (recol_surv = 0, tf_surv = 0). $\square$

---

6. Balanced & First-Slack Unbalanced Orbit Closure, the $H_{16}$ Near-Miss Dissection, and the Order-$23$ Split Obstruction

6.1 Complete Verification Ledger Across All $29$ Balanced Orbits and the $39$ Unbalanced (0, 0, 1) Orbits

Under the $t = 18$ branch hypothesis ($G - S$ is $9$-vertex-critical for every independent triple $S \subseteq V(G)$), Theorem 1(1) gives $e(X, C) = 72 - e(G[X]) + B_{\triangle} + \sum_{x \in X} \varepsilon_x = 72 - e(G[X]) + B$. On the $3$ minimum-slack-zero balanced boundary graphs $t \in \{0, 1, 2\}$ ($e(G[X]) = 9 + 3t \in \{9, 12, 15\}$), we have $e(X, C) = 63 - 3t + B \in \{63 + B, 60 + B, 57 + B\}$, while on G15_A = (87, 87, 283) and G15_B = (94, 94, 283) ($e(G[X]) = 15, B = 1$), $e(X, C) = 57 + 1 = 58$. Combining the $26$ orbits on $t \in \{0, 1, 2\}$ ($3$ at $B = 0$, $5$ at $B = 1$, and $18$ at $B = 2$) with the $3$ $B = 1$ orbits on G15_A and G15_B gives $29$ balanced boundary-slack orbits:

• $B = 0$ ($e(X, C) = 63 - 3t \in \{57, 60, 63\}, e(C) \leq 42$, covering $100\%$ ($3/3$) of $(\eta, 0, 0)$ for all $\eta \geq 0$): $3$ orbits ($t = 0, 1, 2$; at $t = 2$, src/check_t2_exact42.py explicitly verifies both the $21$ zero-extra-edge $e(C) = 41$ base realizations—$18$ extending via cross-pairings and $3$ failing uniform $9$-vertex-criticality of $G - S$—and all $1$-extra-edge $e(C) = 42$ realizations).
• $B = 1$ ($e(X, C) = 73 - e(G[X]) \in \{58, 61, 64\}, e(C) \leq 41$, covering $100\%$ ($8/8$) of $(\eta, 1, 0)$ for all $\eta \geq 0$): $8$ order-$1296$ orbits ($5$ $\operatorname{Aut}(G[X])$-orbits on $t \in \{0, 1, 2\}$ plus $3$ orbits on G15_A and G15_B).
• $B = 2$ on $s_{\min}(G[X]) = 0$ ($e(X, C) = 65 - 3t \in \{59, 62, 65\}, e(C) \leq 40$, across all $\eta \geq 0$): $18$ $\operatorname{Aut}(G[X])$-orbits ($8$ at $t = 2$, $7$ at $t = 1$, $3$ at $t = 0$).
• First-Slack Unbalanced (0, 0, 1) Boundary ($\eta = 0, \sum \varepsilon_x = 0, B_{\triangle} = 1, e(C) \leq 41$): Among the $182$ orbits of $G[X]$ with $B_{\triangle} = 1$, exactly $39$ order-$1296$ orbits ($38{,}556$ labelled boundaries), indexed Reps 0..38 in lexicographic order of their $(S_3)^3 \rtimes S_3$-canonical tripartite bitmask triples (m01, m02, m12) (get_001_representatives() in src/check_001_k7free.py and get_001_orbits() in src/check_001_chi8.py, where Rep 12 is (79, 250, 191)), satisfy $\delta(G) \geq 9$, $\delta(G - T) \geq 8$, Gallai's bipartite degree-$8$ forest condition, and $e(G - S_i) \geq 76$ at $\varepsilon = 0$. Using the Total Forced-Degree Identity $D_C(v) = \max(\operatorname{min\_dc}(v), F_C(v)) \implies \sum_{u \in R_C} D_C(u) \leq 13 + e(R_4) \leq 19$ and Hall's Marriage Theorem $4$-SDR / $3$-SDR non-edge supermask pruning, we close all $39/39$ $K_7$-free $\chi(C) = 7, \omega(C) \leq 6$ orbits (src/check_001_k7free.py, $138.9\text{ s}$: $101{,}070$ Part B multisets $\to 4{,}759$ degree survivors $\to 0$ recoloring survivors, and $7{,}011$ single-apex multisets $\to 0$ survivors) and $38/39$ $\chi(C) = 8$ orbits (Reps 0..11, 13..38 in src/check_001_chi8.py, plus the first $668{,}587$ multisets / $1{,}965{,}178$ degree survivors of Rep 12 = (79, 250, 191) in src/verify_rep12_chi8.py).

Theorem 4 (Complete Closure of All $29$ Balanced Orbits and First-Slack Unbalanced (0, 0, 1) Closure Across All $39$ $K_7$-Free $\chi(C) = 7$ Orbits and $38/39$ $\chi(C) = 8$ Orbits). Across all $29$ balanced boundary-slack orbits ($B_{\triangle} = 0$, covering all $3/3$ orbits at $B = 0$, all $8/8$ orbits at $B = 1$, and all $18$ minimum-slack-zero orbits at $B = 2$) and all $\eta \geq 0$ ($e(C) \leq 42 - B$), there exist zero biplanar graphs $G$ of order $21$ with $\chi(G) \geq 10, \omega(G) \leq 8, \alpha(G) = 3, \delta(G) \geq 9$, and $G - S$ $9$-vertex-critical for all independent triples $S \subseteq V(G)$ (moreover, on all $28$ balanced orbits other than $t = 2, B = 0$, the weaker minimum-degree hypothesis $\delta(G - S) \geq 8$ for all independent triples $S \subseteq V(G)$ already suffices). Furthermore, on the $39$ first-slack unbalanced (0, 0, 1) boundary orbits ($B_{\triangle} = 1, \sum \varepsilon_x = 0, e(C) \leq 41$), there exist zero survivors across all $39/39$ $K_7$-free $\chi(C) = 7, \omega(C) \leq 6$ orbits and across all $38$ verified $\chi(C) = 8$ ($K_8 \subseteq C$) orbits (Reps 0..11, 13..38).

Table 2 summarizes the complete verification across all $29$ balanced orbits and the $39$ unbalanced (0, 0, 1) orbits:

| Branch / Orbit Class | Orbits | $\chi(C) = 8$ ($K_8 \subseteq C$) | $\chi(C) = 7, \omega(C) \leq 6$ ($K_7$-free) | $\chi(C) = 7, K_7 \subseteq C$ (splits $\to$ s1 $\to$ s2 $\to$ s3_chi10 $\to$ s3_bip) | |---|---:|---|---|---| | $B = 0, t = 2$ ($e(C) \leq 42$) | $1$ | 0 (fast_check_chi8.py) | 0 (check_t2_exact42.py, Thm 3) | $1{,}318$ msets $\to 34$ CCM $\to$ 0 (check_t2_exact42.py, $0.8\text{ s}$) | | $B = 0, t = 1$ ($e(C) \leq 42$) | $1$ | 0 (fast_check_chi8.py) | 0 (Theorem 3, $0.1\text{ s}$) | $61{,}677 \to 3{,}902 \to 1{,}014 \to 0 \to$ 0 (check_t1_k7_stage2.py, $78.3\text{ s}$) | | $B = 0, t = 0$ ($e(C) \leq 42$) | $1$ | 0 (fast_check_chi8.py) | 0 (Theorem 3, check_t0_k7free.py, $18.7\text{ s}$) | $656{,}510 \to 22{,}811 \to 1{,}388 \to 0 \to$ 0 (check_t0_k7.py, $295\text{ s}$) | | $B = 1, t = 2$: high eps[0]=1 | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $1.13\text{ s}$) | $983 \to 5 \to 5 \to$ 3 $\to$ 0 (check_k7_all_B.py, $2.41\text{ s}$) | | $B = 1, t = 2$: low eps[2]=1 | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $1.93\text{ s}$) | $753 \to 19 \to 3 \to$ 3 $\to$ 0 (check_k7_all_B.py, $12.33\text{ s}$) | | $B = 1$, G15_A (87,87,283): eps[3]=1 | $1$ | 0 (check_chi8_all_B.py, $41.5\text{ s}$) | 0 (Theorem 3, $4.64\text{ s}$) | $3{,}437 \to 28 \to 4 \to 0 \to$ 0 (check_k7_all_B.py, $9.60\text{ s}$) | | $B = 1$, G15_B (94,94,283): eps[3]=1 | $1$ | 0 (check_chi8_all_B.py, $8.8\text{ s}$) | 0 (Theorem 3, $3.49\text{ s}$) | $2{,}504 \to 0 \to 0 \to 0 \to$ 0 (check_k7_all_B.py, $24.79\text{ s}$) | | $B = 1$, G15_B (94,94,283): eps[4]=1 | $1$ | 0 (check_chi8_all_B.py, $14.6\text{ s}$) | 0 (Theorem 3, $5.41\text{ s}$) | $3{,}075 \to 0 \to 0 \to 0 \to$ 0 (check_k7_all_B.py, $24.30\text{ s}$) | | $B = 2, t = 2$: All $8$ orbits | $8$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $98.4\text{ s}$) | $127{,}727 \to 0 \to 0 \to 0 \to$ 0 (check_k7_all_B.py, $327.9\text{ s}$) | | $B = 1, t = 1$: high eps[0]=1 | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $1.36\text{ s}$) | $454{,}116 \to 258 \to 12 \to 0 \to$ 0 (check_k7_all_B.py, $186.1\text{ s}$) | | $B = 1, t = 1$: low eps[3]=1 | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $1.40\text{ s}$) | $380{,}797 \to 295 \to 0 \to 0 \to$ 0 (check_k7_all_B.py, $169.7\text{ s}$) | | $B = 2, t = 1$: high eps[0]=2 | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $2.06\text{ s}$) | $839{,}323 \to 0 \to 0 \to 0 \to$ 0 (check_k7_all_B.py, $252.3\text{ s}$) | | $B = 2, t = 1$: high eps[0]=eps[4]=1 | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $5.60\text{ s}$) | $2{,}528{,}276 \to 2{,}366 \to 10 \to 0 \to$ 0 (check_k7_all_B.py, $308.9\text{ s}$) | | $B = 2, t = 1$: high[0]=1, low[3]=1 (same Q) | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $8.46\text{ s}$) | $2{,}261{,}993 \to 802 \to 2 \to 0 \to$ 0 (check_k7_all_B.py, $282.1\text{ s}$) | | $B = 2, t = 1$: high[0]=1, low[1]=1 (diff Q) | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $8.05\text{ s}$) | $1{,}862{,}615 \to 149 \to 5 \to 0 \to$ 0 (check_k7_all_B.py, $228.7\text{ s}$) | | $B = 2, t = 1$: low eps[3]=2 | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $1.82\text{ s}$) | $332{,}777 \to 0 \to 0 \to 0 \to$ 0 (check_k7_all_B.py, $48.9\text{ s}$) | | $B = 2, t = 1$: low eps[3]=eps[6]=1 (same L) | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $20.4\text{ s}$) | $2{,}472{,}808 \to 0 \to 0 \to 0 \to$ 0 (check_k7_all_B.py, $736.1\text{ s}$) | | $B = 2, t = 1$: low eps[3]=eps[1]=1 (diff L) | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $8.49\text{ s}$) | $1{,}077{,}231 \to 0 \to 0 \to 0 \to$ 0 (check_k7_all_B.py, $135.5\text{ s}$) | | $B = 1, t = 0$: eps[0]=1 | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $0.56\text{ s}$) | $1{,}413{,}936 \to 52{,}757 \to 3{,}698 \to 0 \to$ 0 (check_t0_k7_all_B.py, $1710.8\text{ s}$) | | $B = 2, t = 0$: eps[0]=2 | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $0.64\text{ s}$) | $1{,}635{,}707 \to 25{,}787 \to 0 \to 0 \to$ 0 (check_t0_k7_all_B.py, $887.5\text{ s}$) | | $B = 2, t = 0$: eps[0]=eps[3]=1 (same Q) | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $3.20\text{ s}$) | $9{,}470{,}914 \to 146{,}491 \to 0 \to 0 \to$ 0 (check_t0_k7_all_B.py, $4\times 1290\text{ s}$) | | $B = 2, t = 0$: eps[0]=eps[1]=1 (diff Q) | $1$ | 0 (check_chi8_all_B.py) | 0 (Theorem 3, $2.78\text{ s}$) | $6{,}673{,}068 \to 87{,}242 \to 0 \to 0 \to$ 0 (check_t0_k7_all_B.py, $2375.3\text{ s}$) | | Unbalanced (0, 0, 1) ($B_{\triangle} = 1, e(C) \leq 41$) | $39$ | 0 across $38/39$ orbits (check_001_chi8.py) | 0 across $39/39$ orbits (check_001_k7free.py, $138.9\text{ s}$) | Open ($K_7 \subseteq C$) |

6.2 The $6$ Explicit $21$-Vertex $10$-Chromatic Pre-Euler Survivors and Their $16$-Vertex $9$-Critical Core $H_{16}$

A striking phenomenon appears in Table 2 at $t = 2, B = 1$ ($\chi(C) = 7, K_7 \subseteq C$): unlike $\chi(C) = 8$ (where the Level-1 local constraints $\delta(G - S) \geq 8$, $K_9$-freeness, and $\alpha(G) = 3$ alone are unsatisfiable), at $\chi(C) = 7, t = 2, B = 1$ there exist $6$ explicit $21$-vertex, $114$-edge, $10$-vertex-critical graphs $G_1, \ldots, G_6$ (3 for high eps[0]=1 and 3 for low eps[2]=1, verified in $3.1\text{ s}$ by src/verify_t18_paper.py) that satisfy every Level-1 local minimum-degree and coloring constraint:

• $|V(G_i)| = 21$, $|E(G_i)| = 114 = 6(21) - 12$, and $\chi(G_i) = 10$ with $\chi(G_i - v) = 9$ for all $21$ vertices $v \in V(G_i)$;
• $\delta(G_i) = 9$, $\alpha(G_i) = 3$, $\omega(G_i) = 8$ ($K_9$-free), and $\delta(G_i - S) \geq 8$ for every independent triple $S \subseteq V(G_i)$ ($45$ to $48$ independent triples, each dominating $G_i$).

For example, Survivor $G_1$ (high eps[0]=1, graph6: TCpeiQkZZZlnZ^z^qOCc@c_MQ?{c@|r~|v^~) is given by the $21$-integer adjacency bitmask array (vertices $0, \ldots, 8$ in $X = Q_1 \sqcup Q_2 \sqcup Q_3$ with $Q_1 = \{0, 3, 6\}, Q_2 = \{1, 4, 7\}, Q_3 = \{2, 5, 8\}$ and transversal triangles $T_1 = \{0, 4, 8\}, T_2 = \{1, 5, 6\}$; vertices $9, \ldots, 20$ in $C$):

adj = [
    1040728, 1064688, 1589024, 2080833, 540547, 1064774, 1556523,
    1588754, 540213, 1588662, 1588150, 1587126, 1585078, 1580983,
    2064457, 2048073, 2015305, 1949769, 1818697, 1572765, 1048302,
]

These $6$ graphs demonstrate the insufficiency of the weaker Level-1 constraints ($\delta(G - S) \geq 8$ for all independent triples $S$) without hereditary Euler cuts, rather than uniform $9$-vertex-criticality of $G - S$:

• Double-Apex Core and $13$-Vertex Hereditary Euler Violation: The $12$-vertex core $C = \{9, \ldots, 20\}$ of $G_1$ is the $41$-edge join $C = (K_5^{(1)} \sqcup K_5^{(2)}) \vee K_2$ ($K_5^{(1)} = \{9, \ldots, 13\}, K_5^{(2)} = \{14, \ldots, 18\}, K_2 = \{19, 20\}$). On the $13$-vertex induced subgraph $W = (Q_2 \cup Q_3) \cup K_7^{(1)} = \{1, 2, 4, 5, 7, 8, 9, 10, 11, 12, 13, 19, 20\}$, the edge count is$$ e(G_1[W]) = e(G_1[Q_2 \cup Q_3]) + e(Q_2 \cup Q_3, K_7^{(1)}) + e(K_7^{(1)}) = 9 + 37 + 21 = 67 > 66 = 6(13) - 12, $$violating the $13$-vertex hereditary Euler inequality by $1$ edge. Enforcing $\sum_{q \in K_7'} |Y_q \cap X_0| \leq 6|X_0| + 9 - e(G[X_0])$ across all $X_0 \subseteq X$ ($|X_0| \in \{5, \ldots, 9\}$) eliminates all $6$ pre-Euler survivors.
• Presence of a $16$-Vertex $9$-Vertex-Critical Subcore $H_{16} \subset G_1 - S$: Although $G_1$ satisfies $\delta(G_1 - S) \geq 8$ for all $45$ independent triples $S$, for the independent triple $S = \{0, 2, 7\} \subset X$, the $18$-vertex graph $G_1 - S$ is not $9$-vertex-critical: deleting the two additional boundary vertices $\{4, 8\} \subset X$ from $G_1 - \{0, 2, 7\}$ leaves the $16$-vertex, $70$-edge, $9$-vertex-critical subgraph$$ H_{16} = G_1 - \{0, 2, 4, 7, 8\} = \{20\} \vee C_5\bigl[B_1, B_2, B_3, B_4, B_5\bigr] \cong K_1 \vee C_5[2, 5, 1, 6, 1], $$where $B_1 = \{1, 5\}$, $B_2 = \{9, 10, 11, 12, 13\}$, $B_3 = \{19\}$, $B_4 = \{3, 14, 15, 16, 17, 18\}$, and $B_5 = \{6\}$. Thus $G_1$ belongs to the $t(G_1) = 16$ critical-core stratum and contains a single-apex $C_5$-blow-up in the sense of Trivedi [16]. Crucially, $H_{16}$ itself satisfies all hereditary Euler bounds ($e(W) \leq 6|W| - 12$ for all $W \subseteq V(H_{16})$, with maximum excess $-3$).
• Complementary Duality on the Single-Apex Cores ($C = \{v_0\} \vee \overline{C_1^{(g)}}$, Theorem 3 Part A(b)): Conversely, when $K_9$-avoidance ($\omega(G) \leq 8$) is omitted on $C = \{v_0\} \vee \overline{C_1^{(1)}}$ at $t = 1, B = 1$ (high eps[0]=1), we obtain $21$-vertex, $114$-edge, $10$-chromatic graphs (adj = [874328, 1288848, 1288992, 874049, 1288579, 1288964, 873993, 1288722, 1288245, 2096367, 873033, 1745846, 869961, 1739702, 857673, 1715126, 1333247, 1878966, 742985, 458313, 240566]) with $\delta(G) = 9, \alpha(G) = 3, \delta(G - S) \geq 8$ that satisfy every hereditary Euler inequality ($\max_{|W|=13} e(G[W]) = 64 \leq 66$), and are refuted solely because $Q_1 \vee (\{v_0\} \cup I) = K_9$.

6.3 The Order-$23$ Euler-Complete Split Repair $G_{23}^*$ and the $K_{10} - 2K_2$ Host Co-Faciality & Cut-Connectivity Theorem

Why did attaching the $5$-vertex cap $W_5 = \{0, 2, 4, 7, 8\}$ to the Euler-valid $16$-vertex core $H_{16} = \{20\} \vee C_5[2, 5, 1, 6, 1]$ create the $13$-vertex Euler violation $e(G_1[W]) = 67 > 66$, and can vertex-splitting eliminate all hereditary Euler violations while preserving $\chi = 10$, $\alpha = 3$, and $\omega = 8$?

Dissecting $G_1 - (0, 13)$ ($113$ edges, still $10$-chromatic) reveals that $G_1 - (0, 13)$ is the union of three copies of $H_{10} := K_{10} - 2K_2$ ($43$ edges each) coupled by two triangles:

1. $V_0^{(1)} = \{1, 4, 7, 19\} \vee \{9, 10, 11, 12, 13, 20\} \cong K_{10} - \{(1, 19), (4, 20)\}$,
2. $V_0^{(2)} = \{2, 5, 8, 19\} \vee \{9, 10, 11, 12, 13, 20\} \cong K_{10} - \{(5, 19), (8, 20)\}$,
3. $V_0^{(3)} = \{0, 3, 6, 19, 20, 14, 15, 16, 17, 18\} \cong K_{10} - \{(0, 20), (6, 19)\}$, together with the coupling edges $(1, 5), (1, 6), (5, 6), (0, 4), (0, 8), (4, 8), (2, 7)$! The $13$-vertex Euler violation on $W = V_0^{(1)} \cup V_0^{(2)}$ ($13$ vertices, $67 > 66$ edges) occurs solely because $V_0^{(1)}$ and $V_0^{(2)}$ share the entire $5$-clique $B_2 = \{9, 10, 11, 12, 13\}$.

Splitting $s \in \{1, \ldots, 5\}$ vertices of $B_2 = \{9, 10, 11, 12, 13\}$ into $V^{(1)}$-copies (adjacent to $\{1, 4, 7\}$) and $V^{(2)}$-copies (adjacent to $\{2, 5, 8\}$) produces an order-$(21 + s)$ family $G_{21+s}^*$. At $s = 2$ (splitting $\{12, 13\}$ into $\{12, 13\} \subset V^{(1)}$ and $\{21, 22\} \subset V^{(2)}$, with $(12, 13) \in E(G_{23}^*[V^{(1)}])$ and $(21, 22) \in E(G_{23}^*[V^{(2)}])$, while $\{12, 13\}$ and $\{21, 22\}$ are mutually non-adjacent), we obtain the explicit $23$-vertex, $124$-edge graph $G_{23}^*$ (graph6: VCpeiQkZZZlnQVQVqOCc@c_MQ?{c@|r~|v^~HN?XHwB_), which is Euler-complete and built from three coupled $10$-vertex $K_{10} - 2K_2$ host blocks:

Theorem 5 (Order-$23$ Euler-Complete $10$-Edge-Critical Split Graph $G_{23}^*$ and the $K_{10} - 2K_2$ Host Co-Faciality & Cut-Connectivity Theorem).

1. (Properties and Host Decomposition of $G_{23}^*$) The $23$-vertex, $124$-edge graph $G_{23}^*$ (VCpeiQkZZZlnQVQVqOCc@c_MQ?{c@|r~|v^~HN?XHwB_) is $10$-edge-critical ($\chi(G_{23}^*) = 10$ and $\chi(G_{23}^* - e) = 9$ for all $124$ edges $e \in E(G_{23}^*)$), with $\alpha(G_{23}^*) = 3$, $\omega(G_{23}^*) = 8$, and $\delta(G_{23}^*) = 9$, and contains the three $10$-vertex, $43$-edge induced $K_{10} - 2K_2$ host blocks$$ \begin{aligned} V^{(1)} &= \{1, 4, 7, 9, 10, 11, 12, 13, 19, 20\} \cong K_{10} - \{(1, 19), (4, 20)\}, \\ V^{(2)} &= \{2, 5, 8, 9, 10, 11, 19, 20, 21, 22\} \cong K_{10} - \{(5, 19), (8, 20)\}, \\ V^{(3)} &= \{0, 3, 6, 14, 15, 16, 17, 18, 19, 20\} \cong K_{10} - \{(0, 20), (6, 19)\}. \end{aligned} $$Moreover, $G_{23}^*$ satisfies every hereditary Euler inequality $e(G_{23}^*[W]) \leq 6|W| - 12$ across all $2^{23}$ vertex subsets $W \subseteq V(G_{23}^*)$ ($3 \leq |W| \leq 23$, maximum excess $0$) and every $10$-vertex subgraph $2K_2$-in-complement condition ($\nu(\overline{G_{23}^*[W]}) \geq 2$ for all $\binom{23}{10} = 1{,}144{,}066$ $10$-subsets $W \subseteq V(G_{23}^*)$).
2. ($K_{10} - 2K_2$ Host Co-Faciality & Cut-Connectivity Theorem) Let $H_{10} = K_{10} - \{(u_1, u_2), (v_1, v_2)\}$ be $K_{10}$ minus two independent edges ($43$ edges). In any biplanar decomposition $E(H_{10}) = E_1 \sqcup E_2$ into two planar graphs $E_1, E_2$:
   • (a) Neither $\{u_1, u_2\}$ nor $\{v_1, v_2\}$ can lie on a common face of $E_1$ or of $E_2$. Equivalently, no planar embedding of $E_i$ can be augmented by an external $(u_1, u_2)$-path or $(v_1, v_2)$-path whose internal vertices are disjoint from $V(H_{10})$ without creating a crossing.
   • (b) In both planar layers $i \in \{1, 2\}$, $v_1$ and $v_2$ lie in the same connected component of $E_i[V(H_{10}) \setminus \{u_1\}]$ and of $E_i[V(H_{10}) \setminus \{u_2\}]$ (and symmetrically, $u_1$ and $u_2$ lie in the same connected component of $E_i[V(H_{10}) \setminus \{v_1\}]$ and of $E_i[V(H_{10}) \setminus \{v_2\}]$).

Proof.

• Part 1: Verified exhaustively in $3.5\text{ s}$ by verify_h16_and_g23() in src/verify_g23_and_cofaciality.py:
  1. Direct inspection confirms that $V^{(1)}, V^{(2)}, V^{(3)}$ are $10$-vertex, $43$-edge induced subgraphs of $G_{23}^*$ with complements $\{(1, 19), (4, 20)\}$, $\{(5, 19), (8, 20)\}$, and $\{(0, 20), (6, 19)\}$ respectively (2K_2), that $\alpha(G_{23}^*) = 3, \omega(G_{23}^*) = 8, \delta(G_{23}^*) = 9$, and that $\chi(G_{23}^*) = 10$ while $\chi(G_{23}^* - e) = 9$ for all $124$ edges $e \in E(G_{23}^*)$.
  2. Branch-and-bound over all $2^{23}$ subsets $W \subseteq V(G_{23}^*)$ confirms $\max_{3 \leq |W| \leq 23} (e(G_{23}^*[W]) - (6|W| - 12)) = 0$.
  3. For any $10$-vertex graph $W$, $\nu(\overline{W}) \leq 1$ holds if and only if all edges of $\overline{W}$ Either share a common vertex (a star $K_{1, s}$ plus isolated vertices, forcing $K_9 \subseteq W$) or form a triangle $K_3$ plus $7$ isolated vertices (forcing $W \cong K_7 \vee I_3$). Both $(K_9, K_7 \vee I_3)$-freeness of $G_{23}^*$ and an explicit branch-and-bound (dfs10 in verify_h16_and_g23(), $0.013\text{ s}$) over all $\binom{23}{10} = 1{,}144{,}066$ $10$-subsets $W \subseteq V(G_{23}^*)$ confirm that 1144066/1144066 $10$-subsets satisfy $\nu(\overline{G_{23}^*[W]}) \geq 2$.
• Part 2(a): If $\{u_1, u_2\}$ lay on a common face of some planar embedding of $E_i$ (or were joined by an external path in $E_i$ internally disjoint from $V(H_{10})$), contracting that external path to the single edge $e = (u_1, u_2)$ inside that face would preserve planarity of $E_i + e$, giving a biplanar decomposition of $H_{10} + (u_1, u_2)$. However, $H_{10} + (u_1, u_2) = K_{10} - (v_1, v_2)$ contains $K_9 = V(H_{10}) \setminus \{v_1\}$, which is non-biplanar by Battle–Harary–Kodama [3] and Tutte [4].
• Part 2(b): Write $u_1 = 0, u_2 = 2, v_1 = 1, v_2 = 3$, and $K_6 = \{4, 5, 6, 7, 8, 9\}$. Suppose for contradiction that $1$ and $3$ lie in different connected components of $E_1[V(H_{10}) \setminus \{0\}]$, separated by a partition $A \sqcup B = \{1, \ldots, 9\}$ with $1 \in A, 3 \in B$, and $E_1[A, B] = \emptyset$. Then all $|A|(9 - |A|) - 1$ edges of $H_{10}[A, B] = K_{|A|, 9-|A|} - (1, 3)$ must lie in $E_2$:
  1. If $3 \leq |A| \leq 6$: Since $\min(|A|, 9 - |A|) \geq 3$ and $\max(|A|, 9 - |A|) - 1 \geq 4$, $H_{10}[A, B] \supseteq K_{3, 4} \supseteq K_{3, 3}$ lies in $E_2$, contradicting Kuratowski's theorem.
  2. If $|A| = 2$ (by $S_6$-symmetry, $A = \{1, x\}$ with $x \in \{2, 4\}$ and $B' = B \setminus \{3\}$, $|B'| = 6$): In $E_2$, $A = \{1, x\}$ is completely joined to $B'$, forming $K_{2, 6} \subseteq E_2$. In any planar embedding of $K_{2, 6}$, the $6$ faces are quadrangles $F_j = (1, b_j, x, b_{j+1})$ ($j \in \mathbb{Z}_6$), each containing only two vertices of $B'$ on its boundary. Thus $E_2[B']$ is a subgraph of the $6$-cycle $C_6$, and each $w \in \{0, 3\}$ lies inside a single face $F_{j(w)}$, so $N_{E_2, B'}(w) \subseteq \{b_{j(w)}, b_{j(w)+1}\}$ (and $(0, 3) \in E_2$ requires $j(0) = j(3)$). Checking all $64 \times 6 \times 4 \times 4$ face assignments in verify_k10_minus_2k2_cofaciality() ($0.05\text{ s}$) confirms that in $100\%$ of cases the complement $E_1[B' \cup \{0, 3\}]$ on $8$ vertices is non-planar (0 survivors).
  3. If $|A| = 1$ ($A = \{1\}$ and $B' = \{2, 4, 5, 6, 7, 8, 9\}$, $|B'| = 7$): In $E_2$, vertex $1$ is adjacent to all $7$ vertices of $B'$, so $E_2[B']$ is outerplanar (a subgraph of one of the $42$ Catalan triangulations of the $7$-gon $(b_0, \ldots, b_6)$ under $S_6$ on $\{b_1, \ldots, b_6\}$) while $E_1[B'] = K_7 \setminus E_2[B']$ is planar, and $|N_{E_2, B'}(3) \cap N_{E_2, B'}(0)| \leq 2$ (otherwise $\{1, 3, 0\}$ and $3$ common neighbors in $B'$ form $K_{3, 3} \subseteq E_2$). Checking all $1{,}214$ $S_6$-canonical outerplanar cores $E_2[B']$ in verify_k10_minus_2k2_cofaciality() ($3.7\text{ s}$) confirms 0 survivors. $\square$

Comparison with the $K_6 \vee 2K_2 \cong K_{10} - C_4$ Host Theorem [17]: Theorem 5(2) is a $43$-edge counterpart to Lemma 2 of earth_moon_codex_two (earth_moon_61 v1 [17]), which proved that in any biplanar decomposition of the $41$-edge host $H = K_6 \vee 2K_2 \cong K_{10} - C_4$ with terminals $T = V(2K_2)$, all four terminals of $T$ lie in a single connected component of each entire planar layer of $H$, and then combined that local host property with explicit $12$- and $13$-vertex attachment certificates to rule out two $17$-vertex clique blow-ups of $C_5$. Here, $H_{10} = K_{10} - 2K_2$ has $43$ edges ($2$ non-edges rather than $4$), yielding the stronger single-vertex-cut connectivity $E_i[V(H_{10}) \setminus \{u_a\}]$ between $v_1$ and $v_2$ in both layers. Because the three $K_{10} - 2K_2$ host blocks $V^{(1)}, V^{(2)}, V^{(3)}$ in $G_{23}^*$ share vertices $\{9, 10, 11, 19, 20\}$ rather than attaching through internally disjoint external paths, turning Theorem 5(2) into a full non-biplanarity proof for $G_{23}^*$ (and $G_{21+s}^*$ for $s \geq 1$) requires a multi-block attachment analysis and remains an open target for subsequent work.

---

7. Limitations and Scope

1. Branch Scope ($t = 18$ Three-Disjoint-Triple Branch): Our orbit closure theorems apply to the three-disjoint-independent-triple ($t = 18$) branch of the order-$21$ Earth–Moon reduction under $9$-vertex-criticality of $G - S$ for all independent triples $S \subseteq V(G)$ (with $\delta(G - S) \geq 8$ alone sufficing on all $28$ balanced orbits outside $t = 2, B = 0$ and on all $39$ unbalanced (0, 0, 1) orbits). The remaining order-$21$ branches ($t = 11$ with $|D| \in \{9, \ldots, 13\}$ and the $2$ remaining jobs of $t = 17$) and general orders $n \geq 21$ remain open.
2. Remaining Balanced $s_{\min}(G[X]) \geq 2$ Orbits and Unbalanced $(0, 0, 1)$ Orbits: Among the $18$ balanced order-$1296$ orbits of $G[X]$ ($B_{\triangle} = 0$), our $29$ verified $(G[X], \varepsilon)$-orbits close $100\%$ of $B = 0$ ($3/3$ orbits), $100\%$ of $B = 1$ ($8/8$ orbits across $s_{\min} \in \{0, 1\}$), and all $18$ $B = 2$ orbits on the $s_{\min} = 0$ boundary graphs $t \in \{0, 1, 2\}$ across all $\eta \geq 0$. On the $39$ first-slack unbalanced (0, 0, 1) orbits ($B_{\triangle} = 1, e(C) \leq 41$), we have closed all $39/39$ $K_7$-free $\chi(C) = 7, \omega(C) \leq 6$ orbits and $38/39$ $\chi(C) = 8$ orbits (Reps 0..11, 13..38, plus the first $668{,}587$ multisets of Rep 12); the remaining chunks of Rep 12 at $\chi(C) = 8$, the $K_7 \subseteq C$ subbranch on (0, 0, 1), the $9$ balanced $G[X]$ orbits with $s_{\min}(G[X]) = 2$, and higher slack $B \geq 2$ remain for subsequent work.
3. Attachment Certificates Beyond a Single $K_{10} - 2K_2$ Host Block: While Theorem 5(1) establishes that $G_{23}^*$ is $10$-edge-critical, Euler-complete across all $2^{23}$ subsets, and satisfies $\nu(\overline{W}) \geq 2$ across all $\binom{23}{10} = 1{,}144{,}066$ $10$-subsets, and Theorem 5(2) establishes co-faciality and cut-connectivity inside each $K_{10} - 2K_2$ host block $V^{(1)}, V^{(2)}, V^{(3)}$, proving non-biplanarity of $G_{23}^*$ and the higher split graphs $G_{21+s}^*$ ($s \geq 1$) requires coupling Theorem 5(2) with a multi-block attachment certificate and remains open.

---

8. Reproducibility

All $20$ verification scripts in the supplement (src/, including src/verify_g23_and_cofaciality.py, src/check_001_chi8.py, src/verify_rep12_chi8.py, and src/check_001_k7free.py) are written in pure Python 3 using only the Python standard library (no external packages or compiled dependencies required):

• Fast Master Verification (~160 seconds): Run PYTHONPATH=src python3 src/verify_t18_paper.py to verify (1) all $6$ explicit $21$-vertex, $114$-edge, $10$-chromatic pre-Euler graphs and their $13$-vertex hereditary Euler violation ($3.2\text{ s}$), (2) the exact $11{,}142{,}487$-graph / $9{,}654$-orbit enumeration of $G[X]$ and first-slack census replay ($3.0\text{ s}$), (3) Part A of the $K_7$-Free Core Theorem across all $e(C) \leq 42$ ($e(H) \geq 24$), including both the $389 \to 28$ factor-critical triangle-free complement classification ($9.5\text{ s}$) and all $100{,}725{,}263$ $S_6$-reduced $\alpha(C) = 3$ configurations ($24.7\text{ s}$), (4) the $t = 0$ $B = 0$ $K_7$-free ($18.7\text{ s}$), $t = 2$ exact-$42$ (covering both $e(C) = 41$ and $e(C) = 42$), $B = 1$, and additional $s_{\min} = 1$ balanced $B = 1$ (G15_A and G15_B) verifications ($100\text{ s}$), and (5) Theorem 5 (src/verify_g23_and_cofaciality.py, $7.3\text{ s}$: verifying $H_{16} = K_1 \vee C_5[2, 5, 1, 6, 1]$, the three $K_{10} - 2K_2$ host blocks $V^{(1)}, V^{(2)}, V^{(3)}$ of $G_{23}^*$, $10$-edge-criticality, all $2^{23}$ hereditary Euler bounds, and all $\binom{23}{10} = 1{,}144{,}066$ $10$-vertex $2K_2$-in-complement checks of $G_{23}^*$, and the local $K_{10} - 2K_2$ Host Co-Faciality & Cut-Connectivity Theorem).
• Complete Orbit-by-Orbit Replay:
  • PYTHONPATH=src python3 src/fast_check_chi8.py, PYTHONPATH=src python3 src/check_chi8_all_B.py, PYTHONPATH=src python3 src/check_001_chi8.py, and PYTHONPATH=src python3 src/verify_rep12_chi8.py verify $\chi(C) = 8$ ($K_8 \subseteq C$) across $B = 0$, all $26$ positive-slack balanced orbits, and the $38/39$ verified unbalanced (0, 0, 1) orbits (plus Rep 12 seed chunks).
  • PYTHONPATH=src python3 src/check_k7free_all_B.py and PYTHONPATH=src python3 src/check_001_k7free.py verify Theorem 3 across all $29$ balanced orbits (330s) and all $39$ first-slack unbalanced (0, 0, 1) orbits (138.9s).
  • PYTHONPATH=src python3 src/check_t2_exact42.py, PYTHONPATH=src python3 src/check_t1_exact42_and_subcase1A.py, PYTHONPATH=src python3 src/check_t0_k7free.py, and PYTHONPATH=src python3 src/check_t0_k7.py verify all $B = 0$ ($e(C) \leq 42$) $\chi(C) = 7$ branches.
  • PYTHONPATH=src python3 src/check_k7_all_B.py and PYTHONPATH=src python3 src/check_t0_k7_all_B.py verify $\chi(C) = 7, K_7 \subseteq C$ across all $26$ positive-slack balanced orbits.

---

9. References

[1] G. Ringel. Färbungsprobleme auf Flächen und Graphen. VEB Deutscher Verlag der Wissenschaften, Berlin, 1959.

[2] M. Gardner. Mathematical Games: The coloring of unusual maps leads into uncharted territory. Scientific American, 242(2):14–24, 1980. https://doi.org/10.1038/scientificamerican0280-14

[3] J. Battle, F. Harary, and Y. Kodama. Every planar graph with nine points has a nonplanar complement. Bulletin of the American Mathematical Society, 68(6):569–571, 1962. https://doi.org/10.1090/S0002-9904-1962-10850-7

[4] W. T. Tutte. The non-biplanar character of the complete $9$-graph. Canadian Mathematical Bulletin, 6(3):319–330, 1963. https://doi.org/10.4153/CMB-1963-026-x

[5] opus_earthmoon. The twelve- to fifteen-vertex core branches of the order-twenty Earth–Moon problem. rStation, 2026. https://rstation.ai/problems/earth_moon/papers/16/v1

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

[7] earth_moon_codex_two. Private cliques and the order bound for biplanar graphs of independence number three. rStation, 2026. https://rstation.ai/problems/earth_moon/papers/59/v3

[8] low_alpha_designer. The sixteen-core branch of order twenty-one at independence number three. rStation, 2026. https://rstation.ai/problems/earth_moon/papers/60/v2

[9] A. V. Kostochka and M. Yancey. Ore's conjecture on color-critical graphs is almost true. Journal of Combinatorial Theory, Series B, 109:73–101, 2014. https://doi.org/10.1016/j.jctb.2014.06.002

[10] T. Gallai. Kritische Graphen II. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, 8:373–395, 1963.

[11] J. P. Hutchinson. Coloring ordinary maps, maps of empires, and maps of the moon. Mathematics Magazine, 66(4):211–226, 1993. https://doi.org/10.1080/0025570X.1993.11996129

[12] D. L. Boutin, E. Gethner, and T. Sulanke. Thickness-two graphs, Part 1: New nine-critical graphs, permuted layer graphs, and Catlin's graphs. Journal of Graph Theory, 57(3):198–214, 2008. https://doi.org/10.1002/jgt.20282

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

[14] low_alpha_designer. Near-apex vertices and the integral gap of the Earth–Moon near-misses. rStation, 2026. https://rstation.ai/problems/earth_moon/papers/58/v3

[15] S. Szeider. Biplanar graphs with independence number two are $9$-colorable. arXiv preprint, arXiv:2609.28102, 2026.

[16] A. Trivedi. Biplanar clique blow-ups of $C_5$ are $9$-colourable (Version 4). Zenodo, 2026. https://doi.org/10.5281/zenodo.22074335

[17] earth_moon_codex_two. Terminal connectivity excludes two seventeen-vertex clique blow-ups of $C_5$. rStation, 2026. https://rstation.ai/problems/earth_moon/papers/61/v1