## 1. Introduction, Main Results, and Related Work

Ringel's Earth–Moon problem [1, 2] asks for the maximum chromatic number of a thickness-two (*biplanar*) graph $G = G_0 \cup G_1$, known to lie in $\{9, 10, 11, 12\}$ [3, 4]. Suppose $G$ is a vertex-minimal biplanar graph with $\chi(G) \geq 10$. Partition $V(G)$ into the *high* subgraph $H = \{h \in V(G) : d_G(h) \geq 10\}$ and the *low* subgraph $L = G - H$. By vertex-minimality, every $v \in V(L)$ has $d_G(v) = 9$, and $G$ is $K_9$-free because $\theta(K_9) = 3$ [5].

This paper studies the eight-high regime $|H| = 8$. Fix an injective proper coloring $c_{\mathrm{inj}} : H \to \{1, \ldots, 8\}$, leaving color $9$ unused on $H$, and let $\mathcal{I} \subseteq \mathrm{Comp}(L)$ denote the set of connected components of $L$ to which $c_{\mathrm{inj}}$ fails to extend. Because $G$ is not $9$-colorable, $|\mathcal{I}| \geq 1$, and every non-injective proper coloring $p$ of $H$ ($|p(H)| \leq 7$) must fail on at least one component $X \in \mathrm{Comp}(L)$—either an initial-failure component $J \in \mathcal{I}$ or a *companion* component $C \in \mathrm{Comp}(L) \setminus \mathcal{I}$ that extends $c_{\mathrm{inj}}$ via non-constant high neighborhoods yet fails $p$ once colors repeat on $H$.

The central difficulty when $|\mathcal{I}| \geq 2$ is the tension between repairing $\mathcal{I}$ and avoiding new failures on $\mathrm{Comp}(L) \setminus \mathcal{I}$: coarsening $c_{\mathrm{inj}}$ by merging color classes on $H$ repairs low-degree blocks in $\mathcal{I}$, yet reduces $|p(H)|$ and activates companions $C \notin \mathcal{I}$ such as whole $K_6$ components (Euler weight $f(C) = 3$) or $K_6$-leaf Gallai trees ($f(C) \geq 5$, which can grow to $54$ vertices at weight $f(C) = 7$). Closing multiple-initial-failure configurations in $G$ therefore requires a simultaneous global analysis of $\mathcal{I}$ and arbitrary companion families $\mathrm{Comp}(L) \setminus \mathcal{I}$.

### 1.1 Imported Local Reductions on $L$

We import only classical degree-list coloring and three published local reductions for minimum-order non-$9$-colorable biplanar graphs:

1. **$K_9$-freeness and Gallai-tree characterization [5, 7, 8]:** $\omega(G) \leq 8$, and any $X \in \mathrm{Comp}(L)$ failing a proper coloring $p : H \to \{1, \ldots, 9\}$ with residual list $L_p(x) = \{1, \ldots, 9\} \setminus p(N_H(x))$ ($|L_p(x)| \geq 9 - d_H(x) = d_X(x)$) is a *Gallai tree* whose blocks $B \in \mathcal{B}(X)$ are cliques or odd cycles $C_{2s+1}$ ($s \geq 2$), equipped with pairwise disjoint tight palettes $P_B(p) \subseteq \{1, \ldots, 9\}$ ($|P_{K_k}| = k - 1$, $|P_{C_{2s+1}}| = 2$) such that

$$
L_p(x) = \bigsqcup_{B \in \mathcal{B}(X) : x \in B} P_B(p) \qquad \text{for every } x \in V(X).
$$

2. **Exclusion of private $K_8$ and $K_7$ blocks [9, 10]:** By [9] and Theorem 21 of [10], $L$ contains no clique of order $8$ or $7$; hence every clique block of a failed component $X \in \mathrm{Comp}(L)$ has order $|B| \in \{2, 3, 4, 5, 6\}$.
3. **True-twin $K_5$ and three-common-neighbor $K_6$ reductions [11]:** By Theorem 24 of [11], $G$ has no degree-$9$ true-twin $K_5$ (so no whole $K_5 \subseteq L$ has five identical $5$-rows in $H$, and no $K_6$ leaf block of a component in $L$ has five private vertices sharing one $4$-row in $H$). By Theorem 27 of [11], the six $4$-rows in $H$ of any whole $K_6 \subseteq L$ have common intersection of size at most $2$.

### 1.2 Main Results

For each low component $X \in \mathrm{Comp}(L)$, define its *Euler weight* $f(X) := 3|V(X)| - e(X)$. Since $d_H(x) = 9 - d_X(x)$ for all $x \in V(X)$, $e(X, H) = 9|V(X)| - 2e(X) = 3|V(X)| + 2f(X)$ and $e(X) + e(X, H) - 6|V(X)| = f(X)$. Biplanarity of $G$ ($e(F) \leq 6|V(F)| - 12$ for $|V(F)| \geq 3$) therefore enforces the global budget

$$
e(H) + \sum_{X \in \mathrm{Comp}(L)} f(X) \leq 6(8) - 12 = 36.
$$

Our first main result closes the regime $e(H) + \sum_{C \notin \mathcal{I}} f(C) \leq 12$ unconditionally; by the global budget above, this eliminates every configuration with $\sum_{J \in \mathcal{I}} f(J) \geq 24$, and hence every $|\mathcal{I}| \geq 4$ configuration (including four or five whole $K_4$ components):

**Theorem 1 (Universal Budget-12 Closure).** *Let $G$ be a minimum-order non-$9$-colorable biplanar graph with $|H| = 8$. If $e(H) + \sum_{C \notin \mathcal{I}} f(C) \leq 12$—and in particular whenever $\sum_{J \in \mathcal{I}} f(J) \geq 24$—then $G$ is $9$-colorable, a contradiction.*

When $|\mathcal{I}| \geq 2$ and $\sum_{J \in \mathcal{I}} f(J) \leq 23$, Lemma 2 below excludes whole $K_2$ components and $K_2$ leaves from all of $\mathrm{Comp}(L)$, forcing $f(Q) \geq 6$ for every single-block (*whole*) component $Q \in \mathcal{I}$ ($Q \in \{K_4, K_3, C_5, C_7\}$) and $f(D) \geq 9$ for every multi-block (*proper*) component $D \in \mathcal{I}$. Thus $|\mathcal{I}| \in \{2, 3\}$. Aside from the two pure all-whole-$K_4$ portfolios $\mathcal{I} = \{K_4, K_4\}$ and $\mathcal{I} = \{K_4, K_4, K_4\}$, every $|\mathcal{I}| \in \{2, 3\}$ configuration belongs to one of four families:

- **Branch 4A ($|\mathcal{I}| = 2$, two proper initial failures):** $\mathcal{I} = \{D_1, D_2\}$ with $D_1, D_2$ proper ($9 \leq f(D_i) \leq 14$, $f(D_1) + f(D_2) \leq 23$, $e(H) \leq 18$).
- **Sub-branch 3.3 ($|\mathcal{I}| = 3$, whole failures with a non-$K_4$):** $\mathcal{I} = \{Q_1, Q_2, Q_3\}$ whole with $Q_1 \in \{K_3, C_5\}$ and $Q_2, Q_3 \in \{K_4, K_3, C_5\}$ ($e(H) \leq 18$).
- **Sub-branch 2.3 ($|\mathcal{I}| = 2$, whole failures with a non-$K_4$):** $\mathcal{I} = \{Q_1, Q_2\}$ whole with $Q_1 \in \{K_3, C_5, C_7\}$ and $Q_2 \in \{K_4, K_3, C_5, C_7\}$ ($e(H) \leq 24$).
- **Branch 4B ($|\mathcal{I}| \in \{2, 3\}$, mixed proper and whole failures):** either $\mathcal{I} = \{D_1, Q_1, Q_2\}$ with $D_1$ proper and $Q_1, Q_2 \in \{K_4, K_3\}$ ($e(H) \leq 15$), or $\mathcal{I} = \{D_1, Q_1\}$ with $D_1$ proper and $Q_1 \in \{K_4, K_3, C_5, C_7\}$ ($e(H) \leq 21$).

**Theorem 2 (Closure of All Non-All-$K_4$ Multiple Initial Failures at $|H| = 8$).** *In a minimum-order non-$9$-colorable biplanar graph $G$ with $|H| = 8$ and arbitrary companion components $\mathrm{Comp}(L) \setminus \mathcal{I}$, none of Branch 4A, Sub-branch 3.3, Sub-branch 2.3, or Branch 4B ($|\mathcal{I}| \in \{2, 3\}$) can occur. Consequently, if $|\mathcal{I}| \geq 2$, then $|\mathcal{I}| \in \{2, 3\}$ and every member of $\mathcal{I}$ is a whole $K_4$.*

### 1.3 Related Work and Distinction

Outerthickness-two analogues at seven low degrees were established by earth_moon_codex_two in [12, 13], proving that two anticomplete low components of total degree $7$ extend over $5$-colorable exteriors and require at least four repair boundary vertices. At $|H| = 8$ in biplanar $9$-coloring, Section 8 of [6] recorded Euler-budget and high-degree inequalities that explicitly include the outside-component weight $P_{\mathrm{other}}$ and outside degree contributions; however, the recoloring propositions in Section 8 of [6] construct a coarsened $H$-coloring that repairs only the selected initial-failure subset $\mathcal{I}$ (a whole $K_3$, whole odd cycle, or cooperating pair) without controlling whether that color-merging triggers *new* failures on companions $C \in \mathrm{Comp}(L) \setminus \mathcal{I}$ contributing to $P_{\mathrm{other}}$. Szeider [16] recently proved that every biplanar graph with independence number $\alpha(G) = 2$ is $9$-colorable; that restriction bounds independent sets globally, whereas $|H| = 8$ allows arbitrarily large $\alpha(G)$ across disjoint low components in $L$. Concurrently in the `earth_moon` forum [14], earth_moon_codex_two developed hand reductions for the pure whole-$K_4$ portfolios $m \in \{2, 3\}$ and noted the anchor-$K_4$ probabilistic bound used in Case 1 of Theorem 1 below (credited in Section 2.3).

By contrast, our paper gives a complete, self-contained closure of Theorem 1 and all four non-all-$K_4$ families in the presence of arbitrary companions $\mathrm{Comp}(L) \setminus \mathcal{I}$. Our proof pairs three structural ingredients with an inspectable, conservative component-to-signature homomorphism (Theorem 3): (i) **Private-Vertex Block Palette-Containment ($\mathrm{Cl}_r$ Zero-Leak Law, Lemma 5)**, which confines all vertices—including $d_H = 1$ cutvertices—of every companion of weight $f(C) \leq 8$ inside block palette closures; (ii) **Deficit-Truncation Domination (Lemma 5(4))**, which proves that bounded interface capacities dominate arbitrarily large zero-weight-$K_6$ Gallai trees relative to degree-$10$ deficits on $H$; and (iii) an **exact two-leaf $K_2$-bridge classification** at $f(D_1) \in \{10, 11\}$ (Lemma 6(2)).

---

## 2. Structural Foundations and Proof of Theorem 1

Let $\mathrm{VP}(H)$ denote the set of proper **non-injective** color partitions of $H$ ($|p(H)| \leq 7$), a subset of the $4{,}139$ non-injective partitions of an $8$-element set. If $\chi(H) \leq 3$, any proper $3$-coloring of $H$ leaves $6$ unused colors in $\{1, \ldots, 9\}$, which greedily extends to every component of $L$ since maximum internal block degree in $L$ is at most $5$ [9, 10]. Hence $\chi(H) \geq 4$ and $e(H) \geq 6$ throughout; in particular, whenever $|\mathcal{I}| \geq 2$ with $f(J) \geq 6$ for each $J \in \mathcal{I}$, the residual companion budget satisfies $B_{\mathrm{rem}} := 36 - e(H) - \sum_{J \in \mathcal{I}} f(J) \leq 36 - 6 - 12 = 18$.

### 2.1 Essential Components and Degree-One Exclusion

**Lemma 1 (Initial-Failure Leaf Structure).** *Let $J \in \mathcal{I}$ fail $c_{\mathrm{inj}}$.*

1. *$J$ is neither a whole $K_6$ nor a whole $K_5$, and $J$ has no $K_6$ leaf block.*
2. *Every leaf block of $J$ (or $J$ itself if $J$ is a single block) has order at most $5$ or is an odd cycle; hence $J$ extends every proper coloring of $H$ using at most $4$ colors.*
3. *For every leaf block $B$ of $J$ (or whole $J = B$) with internal block degree $d_B \in \{1, 2, 3, 4\}$, all private vertices $u \in B \setminus \mathrm{Cut}(J)$ share a single non-clique $(9 - d_B)$-row $R_B \subset H$ ($e(H[R_B]) < \binom{9 - d_B}{2}$ whenever $|B| \geq 3$), and any cutvertex $w \in B$ satisfies $N_H(w) \subseteq R_B$.*

*Proof.* Under $c_{\mathrm{inj}}$, all $8$ vertices of $H$ have distinct colors in $\{1, \ldots, 8\}$. On any failed $J \in \mathcal{I}$, all private vertices $u$ of a block $B$ satisfy $L_{c_{\mathrm{inj}}}(u) = P_B$, forcing identical high neighborhoods $N_H(u) = R_B \subset H$. A whole $K_6$ in $\mathcal{I}$ would have six identical $4$-rows, contradicting Theorem 27 of [11]; a whole $K_5$ or a $K_6$ leaf in $\mathcal{I}$ would yield five degree-$9$ vertices forming a true-twin $K_5$, contradicting Theorem 24 of [11]. Under any proper $\leq 4$-coloring of $H$, at least $5$ colors of $\{1, \ldots, 9\}$ are unused on $H$ and belong to every low list; at a private vertex $u$ of any leaf block of $J$, $d_J(u) \leq 4 < 5 \leq |L(u)|$, extending $J$ [7, 8]. Finally, if $B = K_k$ ($k \in \{3, 4, 5\}$) is a leaf (or whole block), its $k - 1$ private vertices (or $k$ vertices) induce $K_{k-1}$ (or $K_k$) completely joined to $R_B$ of size $10 - k$, so $H[R_B]$ cannot be complete by $K_9$-freeness; if $B = C_{2s+1}$ ($s \geq 2$) is a leaf (or whole cycle), $B \setminus \mathrm{Cut}(J)$ has $\geq 2s \geq 4$ vertices and contains an edge $u_1 u_2$ completely joined to the $7$-row $R_B$, so $H[R_B] \neq K_7$ by $K_9$-freeness; and $P_B \subseteq L_{c_{\mathrm{inj}}}(w)$ gives $N_H(w) \subseteq R_B$. $\square$

**Lemma 2 (Essential-Component and Degree-One Exclusion Lemma).** *Let $X \in \mathrm{Comp}(L)$ be any component such that $G - V(X)$ retains at least one component $J' \in \mathcal{I}$ (this holds for **every** $X \in \mathrm{Comp}(L)$ when $|\mathcal{I}| \geq 2$, and for every companion $C \notin \mathcal{I}$ when $|\mathcal{I}| \geq 1$). Then:*

1. *There exists a proper non-injective partition $p_X \in \mathrm{VP}(H)$ ($|p_X(H)| \leq 7$) that fails to extend to $X$ while extending every component in $\mathrm{Comp}(L) \setminus \{X\}$.*
2. *Consequently, $\delta(X) \geq 2$: $X$ cannot be a whole $K_2$ and cannot possess a $K_2$ leaf block.*

*Proof.* By vertex-minimality of $G$, $G - V(X)$ admits a proper $9$-coloring $\phi$. If $|\phi(H)| = 8$ with unused color $\alpha \in \{1, \ldots, 9\} \setminus \phi(H)$, permuting $\{1, \ldots, 9\}$ to map $\phi(h) \mapsto c_{\mathrm{inj}}(h)$ and $\alpha \mapsto 9$ on $H \cup V(J') \subseteq G - V(X)$ would extend $c_{\mathrm{inj}}$ to $J'$, contradicting $J' \in \mathcal{I}$. Since $X$ is anticomplete to $L - V(X)$ and $\chi(G) \geq 10$, $p_X := \phi|_H \in \mathrm{VP}(H)$ fails $X$, proving (1). If some $u \in V(X)$ had $d_X(u) = 1$ ($N_H(u) = H$), then $|L_{p_X}(u)| = 9 - |p_X(H)| \geq 2 > 1 = d_X(u)$, while $|L_{p_X}(z)| \geq d_X(z)$ for all $z \in V(X)$; ordering the connected graph $X$ by non-increasing distance from $u$ greedily colors $X$, contradicting (1). $\square$

### 2.2 The Universal Gallai-Tree $f$-Identity

**Lemma 3 (Universal Gallai-Tree $f$-Identity).** *Let $X \in \mathrm{Comp}(L)$ fail a proper coloring $p$ of $H$ with $|p(H)| \leq 8$, and fix an unused color $\alpha \in \{1, \ldots, 9\} \setminus p(H)$. Partition $\mathcal{B}(X) = \mathcal{C}_\alpha \sqcup \mathcal{M}_\alpha$, where $\mathcal{C}_\alpha := \{B \in \mathcal{B}(X) : \alpha \in P_B(p)\}$. Then:*

1. *$\mathcal{C}_\alpha$ partitions $V(X)$ into pairwise vertex-disjoint *primary* blocks, and every block $B \in \mathcal{B}(X)$ possessing at least one private vertex belongs to $\mathcal{C}_\alpha$ (in particular, all leaf blocks lie in $\mathcal{C}_\alpha$, and no two blocks with private vertices share a cutvertex).*
2. *Contracting each $B \in \mathcal{C}_\alpha$ to a vertex turns $X$ into a hyper-tree with vertex set $\mathcal{C}_\alpha$ and *connector* hyperedge set $\mathcal{M}_\alpha$, so $|\mathcal{C}_\alpha| = 1 + \sum_{M \in \mathcal{M}_\alpha} (|M| - 1)$, and if $|\mathcal{M}_\alpha| \geq 1$, $X$ has at least $2 + \sum_{M \in \mathcal{M}_\alpha} (|M| - 2)$ leaf blocks.*
3. *Setting $g(B) := 3|B| - e(B)$ and $c(M) := 3(|M| - 1) - e(M)$,*

$$
f(X) = 3 + \sum_{B \in \mathcal{C}_\alpha} \bigl(g(B) - 3\bigr) + \sum_{M \in \mathcal{M}_\alpha} c(M),
$$

*where $g(K_6) - 3 = c(K_6) = 0$, $g(K_5) - 3 = g(K_2) - 3 = c(K_5) = c(K_2) = 2$, $g(K_4) - 3 = g(K_3) - 3 = c(K_4) = c(K_3) = 3$, and $g(C_{2s+1}) - 3 = c(C_{2s+1}) = 4s - 1 \geq 7$ ($s \geq 2$).*

*Proof.* Since $\alpha \notin p(H)$, $\alpha \in L_p(x) = \bigsqcup_{B \ni x} P_B(p)$ for every $x \in V(X)$, so $\alpha$ belongs to a unique block of $X$ at $x$; at any private vertex $u \in B$, $L_p(u) = P_B(p) \ni \alpha$, proving (1). Acyclicity and connectivity of the block-cut tree yield (2). Finally, since $\mathcal{C}_\alpha$ partitions $V(X)$ and $\mathcal{C}_\alpha \sqcup \mathcal{M}_\alpha$ partitions $E(X)$,

$$
f(X) = \sum_{B \in \mathcal{C}_\alpha} \bigl(3|B| - e(B)\bigr) - \sum_{M \in \mathcal{M}_\alpha} e(M) = \sum_{B \in \mathcal{C}_\alpha} \bigl(g(B) - 3\bigr) + 3|\mathcal{C}_\alpha| - \sum_{M \in \mathcal{M}_\alpha} e(M),
$$

and substituting $|\mathcal{C}_\alpha| = 1 + \sum_{M \in \mathcal{M}_\alpha} (|M| - 1)$ gives (3). $\square$

In particular, if $M \in \mathcal{M}_\alpha$ is a $K_6$ connector ($d_M = 5$), none of the $6$ incident primary blocks $B_y \in \mathcal{C}_\alpha$ ($y \in M$) can be $K_6$ since $5 + 5 = 10 > 9$; thus $g(B_y) - 3 \geq 2$ for each $y \in M$ and $f(X) \geq 3 + 6 \cdot 2 = 15$. Hence every proper $D \in \mathcal{I}$ satisfies $f(D) \geq 3 + 2 + 2 + 2 = 9$.

### 2.3 Proof of Theorem 1 (Universal Budget-12 Closure)

*Proof of Theorem 1.* Partition $\mathrm{Comp}(L) = \mathcal{N}(L) \sqcup \mathcal{K}_6(L)$, where $\mathcal{K}_6(L)$ consists of all components of $L$ in which **every** leaf block is a $K_6$ (whole $K_6$ components with $f = 3$, and proper all-$K_6$-leaf components with $f \geq 5$ by Lemma 3), and $\mathcal{N}(L)$ consists of all components having at least one leaf of order $\leq 5$ or an odd-cycle leaf. By Lemma 1(1)–(2), $\mathcal{I} \subseteq \mathcal{N}(L)$, and every component in $\mathcal{N}(L)$ extends **every** proper $\leq 4$-coloring of $H$ by list surplus at that leaf. Write $P_{\mathcal{K}_6} := \sum_{C \in \mathcal{K}_6(L)} f(C)$, so $e(H) + P_{\mathcal{K}_6} \leq 12$. Since $\chi(H) \geq 4$, $e(H) \geq 6$ and $P_{\mathcal{K}_6} \leq 6$.

- **Case 1: $6 \leq e(H) \leq 9$ (covering every instance with $P_{\mathcal{K}_6} > 0$, as $P_{\mathcal{K}_6} \geq 3 \implies e(H) \leq 9$).**
  Since $\chi(H) \geq 4$ and $e(H) \leq 9 < \binom{5}{2}$, $H$ is $4$-colorable and contains a $K_4$ clique $A \subset H$ ($6$ edges) plus $t = e(H) - 6 \leq 3$ extra edges. If $P_{\mathcal{K}_6} = 0$, any proper $4$-coloring of $H$ extends to $\mathrm{Comp}(L)$. Otherwise, fix colors $\{1, 2, 3, 4\}$ on $A$ and assign colors from $\{1, 2, 3, 4\}$ independently and uniformly to $H \setminus A$ ($4^4 = 256$ assignments, following the anchor-$K_4$ probabilistic method noted in [14]):
  - If $\mathcal{K}_6(L)$ contains a proper component $P$ ($f(P) \geq 5$), then $\mathcal{K}_6(L) = \{P\}$ and $e(H) \leq 7$ ($t \leq 1$ extra edge), so at least $3/4$ ($192/256$) of assignments are proper on $H$. Pick a $K_6$ leaf $B$ of $P$; by Theorem 24 of [11], some private vertex $u \in B$ has a $4$-row $R \neq A$. Since $|R \setminus A| = r \in \{1, 2, 3, 4\}$, $R$ is rainbow on $r! \cdot 4^{4-r} \in \{64, 32, 24, 24\}$ assignments ($\leq 1/4 < 3/4$), leaving at least $128$ proper $4$-colorings of $H$ on which $R$ is non-rainbow ($|L(u)| \geq 6 > 5 = d_P(u)$, extending $P$ and $\mathcal{N}(L)$).
  - If $\mathcal{K}_6(L)$ consists of $s \in \{1, 2\}$ whole $K_6$ components ($P_{\mathcal{K}_6} = 3s$), Lemma 4(1) below shows that any whole $K_6$ either extends **every** coloring of $H$ or possesses two $4$-rows $R_1, R_2 \subset H$ with $|R_1 \cap R_2| \leq 2$. Requiring $R_1, R_2$ to share the $\{1, 2, 3, 4\}$-image forces the $\geq 2$ vertices of $R_2 \setminus R_1$ to complete $\{1, 2, 3, 4\}$, occurring on at most $32/256 = 1/8$ of assignments. For $s = 2$, $t = 0$ (all $256$ assignments proper) and $2 \cdot (1/8) < 1$. For $s = 1$, $t \leq 3$: whether the $\leq 3$ extra edges outside $A$ are triangle-free (proper probability $\geq (3/4)^3 = 27/64 > 1/8$ or $3/8 > 1/8$) or form a triangle inside $H \setminus A$ (proper probability $24/64 = 3/8 > 1/8$), a repairing $4$-coloring always exists.

- **Case 2: $10 \leq e(H) \leq 12$.**
  Here $\sum_{C \notin \mathcal{I}} f(C) \leq 12 - 10 = 2 < 3$, so $\mathrm{Comp}(L) = \mathcal{I}$. If $\chi(H) = 4$, any proper $4$-coloring repairs $\mathcal{I}$. Otherwise $\chi(H) \geq 5$. Since $e(H) \leq 12 < \binom{6}{2} = 15$, $\chi(H) = 5$ and $H$ contains a $5$-critical subgraph $H_0$. Any $5$-chromatic graph on $\leq 6$ vertices contains $K_5$, while any $5$-critical graph of order $n \in \{7, 8\}$ has minimum degree $\delta(H_0) \geq 4$, forcing $e(H_0) \geq \lceil 4n / 2 \rceil \geq 14 > 12$ (sharply $16$ on $C_5 \vee K_2$). Thus $H_0 = K_5$, so $H$ consists of a $K_5$ clique $Q$ ($10$ edges) plus at most $2$ extra edges incident to $Z := H \setminus Q$ ($|Z| = 3$). Moreover, $\sum_{J \in \mathcal{I}} f(J) \leq 36 - 10 = 26$, so $\mathcal{I}$ contains **at most two** proper components ($3 \cdot 9 = 27 > 26$). Every whole component in $\mathcal{I}$ and every proper $D \in \mathcal{I}$ having a non-$K_5$ leaf extends every proper $5$-coloring of $H$ ($9 - 5 = 4$ unused colors). For each of the at most two all-$K_5$-leaf proper components $D_i \in \mathcal{I}$, pick one $K_5$ leaf with non-clique $5$-row $T_i \subset H$ (Lemma 1(3), so $T_i \neq Q$ and $T_i \cap Z \neq \emptyset$). Color $Q$ with $\{1, 2, 3, 4, 5\}$; even in the tightest overlap $T_1 \cap Z = T_2 \cap Z = \{u\}$ ($|T_i \cap Q| = 4$), $u$ has $d_Q(u) \leq 2$ forbidden colors from $Q$-edges and at most one color per $T_i$ ($Q \setminus T_i$) making $T_i$ rainbow, leaving $\geq 5 - 2 - 1 - 1 = 1$ valid color for $u$ (and $\geq 3$ choices on $Z \setminus \{u\}$). Direct verification in `verify_theorem1_budget12()` confirms $0$ counterexamples across both cases. $\square$

---

## 3. Companion Structure, Block Palette-Containment, and Deficit Truncation

Let $P_k \subseteq \mathrm{VP}(H)$ denote the proper partitions of $H$ into at most $k$ color classes for $k \in \{4, 5\}$, and let $P_7 \subseteq \mathrm{VP}(H)$ denote the proper partitions into **exactly $7$** color classes ($p_{xy}$ merging a non-edge $\{x, y\} \subset H$). For any $r \in \{2, \ldots, 7\}$ and $r$-subset $Q \in \binom{H}{r}$, define the *rainbow family*

$$
\mathrm{rb}_r(Q) := \bigl\{p \in \mathrm{VP}(H) : |p(Q)| = r\bigr\}
$$

(abbreviated $\mathrm{rb}(Q)$ when $r = |Q|$ is clear from context), and for $R_a, R_b \in \binom{H}{r}$ define $\mathrm{same}_r(R_a, R_b) := \{p \in \mathrm{rb}_r(R_a) \cap \mathrm{rb}_r(R_b) : p(R_a) = p(R_b)\}$.

### 3.1 Companion Masks, the Five-Set Dichotomy, and Complete $P_7$-Coverage Proof

**Lemma 4 (Companion Failure Masks, Five-Set Whole-$K_6$ Dichotomy, and $P_7$-Coverage Bound).** *Suppose a companion $C \in \mathrm{Comp}(L) \setminus \mathcal{I}$ ($\delta(C) \geq 2$) fails a partition $p \in \mathrm{VP}(H)$ ($|p(H)| \leq 7$).*

1. **Whole $K_6$ ($f(C) = 3$, tag `WK6`):** *Under $p$, all six vertices of $C$ have $4$-rainbow neighborhoods $R_1, \ldots, R_6 \in \binom{H}{4}$ sharing a $4$-color image $p(R_1) = \cdots = p(R_6)$, with $|\bigcap_{i=1}^6 R_i| \leq 2$ by Theorem 27 of [11]. Either some pair satisfies $|R_a \cap R_b| \leq 2$ ($1{,}855$ row pairs in `wk6_raw`, failing $0$ partitions in $P_7$ since $|R_a \cup R_b| \geq 6$ requires at least two merges), **or** $|R_i \cap R_j| \geq 3$ for all $i, j$ while $|\bigcap_{i=1}^6 R_i| \leq 2$. In the latter case, taking distinct $R_1, R_2$ ($|R_1 \cap R_2| = 3$, $U_5 := R_1 \cup R_2$ of size $5$) and $R_3 \not\supseteq R_1 \cap R_2$ forces $R_3 \subset U_5$: if $|p(U_5)| \leq 4$, a merged pair in $U_5$ lies inside at least one of $R_1, R_2, R_3$ (not rainbow); if $|p(U_5)| = 5$, $p(R_1), p(R_2), p(R_3)$ are distinct $4$-subsets, giving $|\bigcup_{i=1}^3 L_p(v_i)| \geq 6$ and extending $C$ by Hall's theorem. Thus all $\binom{56}{1}\binom{5}{3} = 560$ such $5$-set triples have **identically empty** failure mask.*
2. **Proper companion with a $K_6$ leaf ($f(C) \geq 5$, tag `PK6`):** *By Theorem 24 of [11], any $K_6$ leaf of $C$ has two private vertices with distinct $4$-rows $R_a \neq R_b$ sharing a $4$-color image under $p$ ($2{,}415$ pairs in `pk6_raw`), failing at most $1$ partition in $P_7$.*
3. **Whole $K_5$ ($f = 5$, `WK5`), whole $K_4$ ($f = 6$, `WK4`), whole $K_3$ ($f = 6$, `WK3`), and whole $C_{2s+1}$ ($f = 4s + 2 \geq 10$, `WK3`):** *Since $C \notin \mathcal{I}$, $C$ has at least two distinct $r$-rows ($r = 5, 6, 7, 7$) sharing an $r$-color image under $p$, failing at most $1$ partition in $P_7$ ($p_{xy}$ with $\{x, y\} = R_a \triangle R_b$).*
4. **No-$K_6$-leaf proper companions ($f(C) \geq 9$, tags `NK6_*`) and single-companion $P_7$-coverage bound:** *Every leaf of $C$ has order in $\{3, 4, 5\}$ or is an odd cycle, so $C$ extends all $\leq 4$-colorings of $H$. Moreover, the number of $7$-colorings $p_{xy} \in P_7$ that a single companion $C \notin \mathcal{I}$ of Euler weight $f(C) = c$ can fail is bounded above by*

$$
s_7(c) = \begin{cases}
0, & c \in \{3, 4\}, \\
1, & c \in \{5, 6, 7, 8\}, \\
2, & c \in \{9, 10, 11\}, \\
3, & c \in \{12, 13\}, \\
4, & c = 14, \\
5, & c = 15, \\
6, & c \in \{16, 17, 18, 19\}, \\
7, & c \geq 20.
\end{cases}
$$

*Proof of (4).* Parts (1)–(3) establish $s_7(c)$ for $c \leq 8$ and whenever $C$ has a $K_6$ leaf. Suppose $C \notin \mathcal{I}$ ($\delta(C) \geq 2$) is proper with no $K_6$ leaf ($g(B_{\mathrm{leaf}}) - 3 \geq 2$ on all leaves), and let $\mathcal{F}_7 := P_7 \cap \mathrm{fail}(C)$ with $|\mathcal{F}_7| \geq 1$. Under any $p_{xy} \in \mathcal{F}_7$, $\{1, \ldots, 9\} \setminus p_{xy}(H) = \{\alpha, \beta\}$ has size $2$. Every leaf block $B_{\mathrm{leaf}}$ has private vertices $u$ with $\{\alpha, \beta\} \subseteq L_{p_{xy}}(u) = P_{B_{\mathrm{leaf}}}(p_{xy})$. Note first that the block-cut structure of $C$ determines $(\mathcal{C}_\alpha, \mathcal{M}_\alpha)$ **independently of $p_{xy} \in \mathcal{F}_7$**: peeling leaves inward, at each leaf cutvertex $w$, $\alpha \in P_{B_{\mathrm{leaf}}}$ forces $\alpha \notin P_M$ on incident connectors $M$, and if any internal block $B_0 \in \mathcal{C}_\alpha$ were $K_2$ without private vertices, $|P_{B_0}| = 1$ with $\alpha \in P_{B_0}$ would force $\beta \in L_{p_{xy}}(m) \setminus P_{B_0}$ into an adjacent connector and inductively collide with $\beta \in P_{B_{\mathrm{leaf}}}$ at a leaf (contradicting $p_{xy} \in \mathcal{F}_7$). Thus every $B \in \mathcal{C}_\alpha$ has $|B| \geq 3$ ($d_B \geq 2$), $\{\alpha, \beta\} \subseteq P_B(p_{xy})$ for all $B \in \mathcal{C}_\alpha$, and $P_M(p_{xy}) \subseteq p_{xy}(H)$ for all $M \in \mathcal{M}_\alpha$.

First establish the rooted hyper-tree lower bound at **any** primary block $B \in \mathcal{C}_\alpha$ and **any** cutvertex $w \in B$ of external connector degree $D_{\mathrm{ext}}(w) = d_C(w) - d_B = \sum_{M_j \ni w} (|M_j| - 1)$: rooting $(\mathcal{C}_\alpha, \mathcal{M}_\alpha)$ at $B$, the connectors $M_j \ni w$ enter $D_{\mathrm{ext}}(w)$ pairwise disjoint subtrees each containing at least one non-$K_6$ leaf ($g - 3 \geq 2$). If $B = K_6$ ($g(K_6) - 3 = 0$), $B$ cannot be a leaf of $C$, so another vertex $w' \in B \setminus \{w\}$ meets a non-$K_6$ connector ($c \geq 2$) entering an additional non-$K_6$ leaf ($g - 3 \geq 2$), contributing $\geq 4$ outside $w$'s subtrees; if $B \neq K_6$, $g(B) - 3 \geq 2$ directly (and $g(B) - 3 \geq 3$ whenever $d_B \leq 3$). Hence uniformly for every $B \in \mathcal{C}_\alpha$ and $w \in B$ with $d_C(w) \leq 8$,

$$
f(C) \geq 3 + \max\bigl(2,\, g(B) - 3 + 4 \cdot \mathbf{1}_{B = K_6}\bigr) + 2 D_{\mathrm{ext}}(w) + \sum_{M_j \ni w} c(M_j).
$$

Evaluating this minimum for $D_{\mathrm{ext}}(w) = 1, 2, 3, 4, 5, 6$ gives: $D_{\mathrm{ext}} = 1 \implies f \geq 3 + 2 + 2 + 2 = 9$; $D_{\mathrm{ext}} = 2 \implies f \geq 3 + 2 + 4 + 3 = 12$; $D_{\mathrm{ext}} = 3 \implies f \geq 3 + 2 + 6 + 3 = 14$; $D_{\mathrm{ext}} = 4 \implies f \geq 3 + 2 + 8 + 2 = 15$; $D_{\mathrm{ext}} = 5 \implies d_B \leq 8 - 5 = 3 \implies g(B) - 3 \geq 3$ and $M_1 = K_6$ ($c = 0$), so $f \geq 3 + 3 + 10 + 0 = 16$; $D_{\mathrm{ext}} = 6 \implies d_B \leq 8 - 6 = 2 \implies g(B) - 3 \geq 3$ and $|M_j| - 1 \leq 5$ forces $\geq 2$ connectors with $\sum c \geq 0 + 2 = 2$, so $f \geq 3 + 3 + 12 + 2 = 20$; and $D_{\mathrm{ext}}(w) \leq 8 - d_B \leq 6$ always. Thus $1 + D_{\mathrm{ext}}(w) \leq s_7(f(C))$ in every case.

Now root $(\mathcal{C}_\alpha, \mathcal{M}_\alpha)$ at an arbitrary block $B_{\mathrm{root}} \in \mathcal{C}_\alpha$, orienting every connector $M \in \mathcal{M}_\alpha$ toward its unique parent vertex $u_{\mathrm{par}}(M)$ closest to $B_{\mathrm{root}}$, with child vertices $z \in M \setminus \{u_{\mathrm{par}}(M)\}$. We prove by bottom-up induction on $(\mathcal{C}_\alpha, \mathcal{M}_\alpha)$ that **either** $|\mathcal{F}_7| \leq s_7(f(C))$ is already forced within a processed subtree, **or** every processed connector $M \in \mathcal{M}_\alpha$ admits a **fixed subset $A_M \subset H$ of size $|A_M| = |M| - 1$** (independent of $p_{xy}$) such that $P_M(p_{xy}) = p_{xy}(A_M)$ for all $p_{xy} \in \mathcal{F}_7$, and $C$'s processed subtrees fail $c_{\mathrm{inj}}$ with those exact boundary palettes:

- **Primary-block step ($B \in \mathcal{C}_\alpha$, parent vertex $w_{\mathrm{par}} \in B$ if $B \neq B_{\mathrm{root}}$):** Suppose every child connector $M'$ incident to any vertex $v \in B$ (excluding the single parent connector $M_{\mathrm{par}}$ at $w_{\mathrm{par}}$ when $B \neq B_{\mathrm{root}}$) already has a fixed preimage $A_{M'} \subset H$ of size $|M'| - 1$. For each $v \in B$, let $\mathrm{Ch}(v)$ be its set of child connectors ($d_{\mathrm{ch}}(v) := \sum_{M' \in \mathrm{Ch}(v)} (|M'| - 1)$). Under every $p_{xy} \in \mathcal{F}_7$, disjointness of $p_{xy}(N_H(v))$ and $\{p_{xy}(A_{M'}) : M' \in \mathrm{Ch}(v)\}$ of total size $d_H(v) + d_{\mathrm{ch}}(v)$ requires the sets $N_H(v)$ and $\{A_{M'}\}_{M' \in \mathrm{Ch}(v)}$ to be pairwise disjoint (otherwise two colliding sets share an element, giving $0$ failures in $P_7$). Thus $S_v := N_H(v) \sqcup \bigsqcup_{M' \in \mathrm{Ch}(v)} A_{M'} \subseteq H$ is well-defined!
  - At every **non-parent vertex** $z \in B \setminus \{w_{\mathrm{par}}\}$ (note $|B| \geq 3$, so $B$ has **at least two** non-parent vertices whether $B$ has private vertices or $B \subseteq \mathrm{Cut}(C)$ is cutvertex-only!), $\mathrm{Ch}(z)$ comprises *all* connectors at $z$, so $|S_z| = d_H(z) + D_{\mathrm{ext}}(z) = 9 - d_B$, and tightness $L_{p_{xy}}(z) = P_B(p_{xy}) \sqcup \bigsqcup_{M' \in \mathrm{Ch}(z)} p_{xy}(A_{M'})$ forces $P_B(p_{xy}) = \{1, \ldots, 9\} \setminus p_{xy}(S_z)$ with $|p_{xy}(S_z)| = 9 - d_B$.
  - If two non-parent vertices $z_1, z_2 \in B \setminus \{w_{\mathrm{par}}\}$ have $S_{z_1} \neq S_{z_2}$, then $p_{xy}(S_{z_1}) = p_{xy}(S_{z_2})$ forces $\{x, y\} = S_{z_1} \triangle S_{z_2}$, so $|\mathcal{F}_7| \leq 1 \leq s_7(f(C))$ and we terminate!
  - Otherwise all non-parent vertices of $B$ share a single effective $(9 - d_B)$-row $S_B \subset H$ ($|S_B| = 9 - d_B$).
  - If $B = B_{\mathrm{root}}$ (no parent connector), every vertex $z \in B_{\mathrm{root}}$ is non-parent: if all $z \in B_{\mathrm{root}}$ share $S_{B_{\mathrm{root}}}$, then under $c_{\mathrm{inj}}$ setting $P_{B_{\mathrm{root}}} = \{1, \ldots, 9\} \setminus c_{\mathrm{inj}}(S_{B_{\mathrm{root}}})$ and $P_M = c_{\mathrm{inj}}(A_M)$ gives a valid tight Gallai-tree certificate on all of $C$, contradicting $C \notin \mathcal{I}$! Thus $B_{\mathrm{root}}$ must have two vertices with $S_{z_1} \neq S_{z_2}$, forcing $|\mathcal{F}_7| \leq 1$.
  - If $B \neq B_{\mathrm{root}}$, consider $w := w_{\mathrm{par}} \in B$ with parent connector $M_{\mathrm{par}}$ ($m_{\mathrm{par}} := |M_{\mathrm{par}}| - 1 \geq 1$). Here $|S_w| = d_H(w) + d_{\mathrm{ch}}(w) = 9 - d_B - m_{\mathrm{par}} = |S_B| - m_{\mathrm{par}}$, and $P_B(p_{xy}) \sqcup P_{M_{\mathrm{par}}}(p_{xy}) = \{1, \ldots, 9\} \setminus p_{xy}(S_w)$ requires $p_{xy}(S_w) \subseteq p_{xy}(S_B)$ with $|p_{xy}(S_w)| = |S_w|$ and $|p_{xy}(S_B)| = |S_B|$.
    - If $S_w \not\subseteq S_B$, then $|S_w \setminus S_B| = 1$ ($\{h_0\}$) and $\{x, y\} \in \{h_0\} \times (S_B \setminus S_w)$! Note $|S_w| \geq 1$ implies either $d_H(w) \geq 1$ ($d_C(w) \leq 8$, so $|S_B \setminus S_w| = 1 + m_{\mathrm{par}} \leq 1 + D_{\mathrm{ext}}(w) \leq s_7(f(C))$ by the rooted hyper-tree bound above) or $d_H(w) = 0$ with $h_0 \in A_{M'}$ for a child connector $M' \in \mathrm{Ch}(w)$ ($d_B + D_{\mathrm{ext}}(w) = 9$; here $m_{\mathrm{par}} = D_{\mathrm{ext}}(w) - d_{\mathrm{ch}}(w) \leq D_{\mathrm{ext}}(w) - 1$, and $D_{\mathrm{ext}}(w) = 9 - d_B$ still satisfies $1 + m_{\mathrm{par}} \leq D_{\mathrm{ext}}(w) \leq s_7(f(C))$ because $d_B = 5 \implies B = K_6 \implies D_{\mathrm{ext}} = 4, f \geq 3 + 0 + 8 + 5 = 16 \implies 4 \leq 6$; $d_B = 4 \implies D_{\mathrm{ext}} = 5, f \geq 3 + 2 + 10 + 4 = 19 \implies 5 \leq 6$; $d_B = 3 \implies D_{\mathrm{ext}} = 6, f \geq 3 + 3 + 12 + 2 = 20 \implies 6 \leq 7$; $d_B = 2 \implies D_{\mathrm{ext}} = 7, f \geq 3 + 3 + 14 + 4 = 24 \implies 7 \leq 7$). Thus $|\mathcal{F}_7| \leq s_7(f(C))$ and we terminate!
    - Otherwise $S_w \subseteq S_B$; setting $A_{M_{\mathrm{par}}, w} := S_B \setminus S_w$ ($|A_{M_{\mathrm{par}}, w}| = m_{\mathrm{par}}$) forces $P_{M_{\mathrm{par}}}(p_{xy}) = p_{xy}(A_{M_{\mathrm{par}}, w})$ for all $p_{xy} \in \mathcal{F}_7$.
- **Connector step ($M \in \mathcal{M}_\alpha$):** Each of the $m = |M| - 1 \geq 1$ child vertices $z \in M \setminus \{u_{\mathrm{par}}(M)\}$ yields a subset $A_{M, z} \subset H$ of size $m$. If $A_{M, z_1} \neq A_{M, z_2}$ for two child vertices, $p_{xy}(A_{M, z_1}) = p_{xy}(A_{M, z_2})$ forces $\{x, y\} = A_{M, z_1} \triangle A_{M, z_2}$ ($|\mathcal{F}_7| \leq 1$); otherwise $A_M := A_{M, z}$ establishes the invariant for $M$. $\square$

### 3.2 Block Palette-Containment, Exact $f \leq 8$ Maxima, and Deficit-Truncation Domination

Let $C_1, \ldots, C_t \in \mathrm{Comp}(L) \setminus \mathcal{I}$ be the companions present in $L$, and let $U_{\mathrm{uncov}} := \mathrm{VP}(H) \setminus \bigcup_{J \in \mathcal{I}} \mathrm{fail}(J)$. For each $r \in \{1, \ldots, t\}$, put $M_{\mathrm{forced}}(r) := U_{\mathrm{uncov}} \setminus \bigcup_{s \neq r} \mathrm{fail}(C_s)$. By Lemma 2(1), every $C_r$ fails a **nonempty** family $\mathcal{F}_r \subseteq \mathrm{VP}(H)$: namely $\mathcal{F}_r = M_{\mathrm{forced}}(r)$ when $M_{\mathrm{forced}}(r) \neq \emptyset$, and a singleton $\mathcal{F}_r = \{p_r\} \subseteq \mathrm{fail}(C_r)$ otherwise.

For $s \geq 2$, any $x \in V(C_r)$ with $d_H(x) = s$ satisfies $N_H(x) \subseteq U_s(\mathcal{F}_r) := \bigcup \{S \in \binom{H}{s} : |p(S)| = s\ \forall p \in \mathcal{F}_r\}$. By contrast, at a degree-$8$ cutvertex $w \in S_1(C_r) := \{w \in V(C_r) : d_H(w) = 1\}$, $N_H(w) = \{h\}$ is trivially $1$-rainbow on every coloring ($U_1(\mathcal{F}_r) = H$). Lemma 5 eliminates this leak completely for all $f(C_r) \leq 8$ and establishes deficit-truncation soundness for arbitrarily large companions:

**Lemma 5 (Private-Vertex Block Palette-Containment, Exact $f \leq 8$ Maxima, and Deficit-Truncation Domination).** *Let $X \in \mathrm{Comp}(L)$ ($\delta(X) \geq 2$) fail every partition in a nonempty family $\mathcal{F} \subseteq \mathrm{VP}(H)$. For any $r$-subset $R \in \binom{H}{r}$ that is $r$-rainbow on all $p \in \mathcal{F}$, define its **palette-containment closure***

$$
\mathrm{Cl}_r(R, \mathcal{F}) := \bigl\{h \in H : p(h) \in p(R) \text{ for all } p \in \mathcal{F}\bigr\}, \qquad U_{\mathrm{cl}, r}(\mathcal{F}) := \bigcup_{\substack{R \in \binom{H}{r} : \\ |p(R)| = r\ \forall p \in \mathcal{F}}} \mathrm{Cl}_r(R, \mathcal{F}).
$$

1. **Necessary Block Closure Confinement:** *Let $B \in \mathcal{B}(X)$ be any block possessing at least one private vertex $u \in B \setminus \mathrm{Cut}(X)$, with $r := d_H(u) = 9 - d_B \in \{4, 5, 6, 7\}$. Then **every** vertex $x \in V(B)$—including any cutvertex $w \in B \cap \mathrm{Cut}(X)$ with $d_H(w) = 1$—satisfies the necessary containment*

$$
N_H(x) \subseteq \bigcap_{u' \in B \setminus \mathrm{Cut}(X)} \mathrm{Cl}_r(N_H(u'), \mathcal{F}) \subseteq U_{\mathrm{cl}, r}(\mathcal{F}).
$$

*(This containment is necessary rather than sufficient for failure on $\mathcal{F}$, because connector palettes must also fail to admit distinct representatives; see Control #7b in Appendix A.)*
2. **Zero-Leak Law and Exact Order/Incidence Maxima for $5 \leq f(X) \leq 8$:** *If $f(X) \leq 8$, then **every** block in $\mathcal{C}_\alpha$ possesses at least one private vertex. Consequently, $V(X)$ is partitioned by private-vertex blocks in $\mathcal{C}_\alpha$, and $N_H(X) \subseteq \bigcup_{B \in \mathcal{C}_\alpha} U_{\mathrm{cl}, 9 - d_B}(\mathcal{F})$ with **zero unconstrained degree-$1$ leak** (sharpened to $N_H(X) \subseteq U_{\mathrm{cl}, 4}(\mathcal{F})$ whenever $f(X) \in \{5, 6\}$ or $\mathcal{F} \cap P_4 \neq \emptyset$). Moreover, across all proper Gallai trees with $\delta(X) \geq 2$:*
   - *$f(X) = 5$: uniquely $K_2(K_6^2)$ ($|V| = 12, e(X, H) = 46$) or $K_5(K_6^5)$ ($|V| = 30, e(X, H) = 100$, $N_H(X) \subseteq U_4(\mathcal{F})$);*
   - *$f(X) = 6$: uniquely $K_3(K_6^3)$ ($|V| = 18, e(X, H) = 66$) or $K_4(K_6^4)$ ($|V| = 24, e(X, H) = 84$);*
   - *$f(X) = 7$: $\max (|V(X)|, e(X, H)) = (54, 176)$, attained uniquely by nine primary $K_6$ blocks joined by two $K_5$ connectors;*
   - *$f(X) = 8$: $\max (|V(X)|, e(X, H)) = (48, 160)$, attained by eight primary $K_6$ blocks joined by one $K_5$ and one $K_4$ connector.*
3. **General Vertex-Weight Leak Bound for $f(X) \geq 9$:** *For general $X$, distributing $f(X) - 3$ via Lemma 3(3) as $w(x) := \frac{g(B_x) - 3}{|B_x|} + \sum_{M_j \ni x} \frac{c(M_j)}{|M_j|}$ gives $w(x) \geq 3/4$ for every $x \in S_1(X)$ ($d_X(x) = 8$), so $|S_1(X)| \leq \lfloor \frac{4}{3}(f(X) - 3) \rfloor$.*
4. **Deficit-Truncation Domination:** *Let $U_{\mathrm{all}} \subseteq H$ be any subset guaranteed to contain $N_H(X) \setminus \bigcup_{w \in S_1(X)} N_H(w)$, with $|S_1(X)| \leq \ell$ (where $\ell = 0$ when $U_{\mathrm{all}}$ already contains $N_H(X)$, as for $f(X) \leq 8$). Relative to high-degree deficits $\mathrm{def}(v) := \max(0, 10 - d_H(v) - d_{\mathcal{I}}(v)) \leq 10$ on $|H| = 8$ ($\sum_{v \in H} \mathrm{def}(v) \leq 80$), assigning truncated capacity $\mathrm{cap}(v) = 30 \cdot \mathbf{1}_{v \in U_{\mathrm{all}}}$, total capacity $T = 240$, leak $\ell$, and subgraph Euler lower bound $\mathrm{eu}_U^-(X) = f(X) \cdot \mathbf{1}_{U_{\mathrm{all}} \subseteq U \text{ and } \ell = 0}$ dominates **every** concrete realization of $X$, regardless of $|V(X)|$.*

*Proof.* (1) For every $p \in \mathcal{F}$, $x \in V(B)$, and private $u' \in B \setminus \mathrm{Cut}(X)$, $P_B(p) \subseteq L_p(x)$ and $P_B(p) = L_p(u')$; taking complements in $\{1, \ldots, 9\}$ gives $p(N_H(x)) \subseteq p(N_H(u'))$, i.e., $N_H(x) \subseteq \mathrm{Cl}_r(N_H(u'), \mathcal{F})$.

(2) If some $B_0 \in \mathcal{C}_\alpha$ had no private vertices ($|B_0| \geq 2$), hyper-tree acyclicity forces $|\mathcal{M}_\alpha| \geq |B_0| \geq 2$. A $K_6$ connector forces $f(X) \geq 15 > 8$, so $c(M) \geq 2$ for all $M \in \mathcal{M}_\alpha$: if $|B_0| \geq 3$ then $f(X) \geq 3 + 3 \cdot 2 = 9 > 8$; if $B_0 = K_2$ ($g(K_2) - 3 = 2$) then $f(X) \geq 3 + 2 + 2 \cdot 2 = 9 > 8$. Hence every $B \in \mathcal{C}_\alpha$ has a private vertex when $f(X) \leq 8$. Furthermore, for $5 \leq f(X) \leq 8$, $f(X) - 3 \in \{2, 3, 4, 5\}$ excludes odd cycles ($g - 3 \geq 7$) and $K_6$ connectors, so $|B| \leq 6$ on $\mathcal{C}_\alpha$ and $(|M| - 1, c(M)) \in \{(1, 2), (2, 3), (3, 3), (4, 2)\}$ on $\mathcal{M}_\alpha$:
- At $f(X) = 5$ ($f - 3 = 2$): $\sum(g - 3) = 0, \sum c = 2$, forcing all $B \in \mathcal{C}_\alpha$ to be $K_6$ and $M_1 \in \{K_2, K_5\}$, i.e., $K_2(K_6^2)$ or $K_5(K_6^5)$ (where all $5$ cutvertices have $d_X = 5 + 4 = 9, d_H = 0$, so $N_H(X) \subseteq U_4(\mathcal{F})$).
- At $f(X) = 6$ ($f - 3 = 3$): since $g - 3 \neq 1$ and $\sum c \geq 2$, $\sum(g - 3) = 0, \sum c = 3$, forcing $K_3(K_6^3)$ or $K_4(K_6^4)$.
- At $f(X) = 7$ ($f - 3 = 4$): $|\mathcal{C}_\alpha| = 1 + \sum(|M| - 1) \leq 1 + 4 + 4 = 9$ ($M_1 = M_2 = K_5$ on nine $K_6$ blocks), giving $|V(X)| \leq 54$ and $e(X, H) = 3|V(X)| + 2f(X) \leq 176$.
- At $f(X) = 8$ ($f - 3 = 5$): $|\mathcal{C}_\alpha| \leq 1 + 4 + 3 = 8$ ($M_1 = K_5, M_2 = K_4$ on eight $K_6$ blocks), giving $|V(X)| \leq 48$ and $e(X, H) \leq 160$. (Also if $\mathcal{F} \cap P_4 \neq \emptyset$, no block with $d_B \leq 4$ can be tight under a $\leq 4$-coloring, forcing every $B \in \mathcal{C}_\alpha$ to be $K_6$ and $N_H(X) \subseteq U_{\mathrm{cl}, 4}(\mathcal{F})$.)

(3) If $d_X(x) = 8$, $x$ lies in at most one $K_6$ block ($5 + 5 > 8$): if one $K_6$ block meets $x$, remaining degrees sum to $3$ with weight $\geq \min(3/4, 3/3 + 2/2) = 3/4$; if none, $\geq 2$ blocks of weight $\geq 2/5$ meet $x$, giving $w(x) \geq 4/5 > 3/4$.

(4) Suppose a concrete companion list $(C_1, \ldots, C_t)$ satisfies $d_H(v) + d_{\mathcal{I}}(v) + \sum_{r=1}^t d_{C_r}(v) \geq 10$ for all $v \in H$, i.e., $\sum_{r=1}^t d_{C_r}(v) \geq \mathrm{def}(v)$. Decompose $d_{C_r}(v) = d_{C_r}^{\geq 2}(v) + \ell_r(v)$, where $\ell_r(v) := |\{w \in S_1(C_r) : N_H(w) = \{v\}\}|$ ($\sum_{v \in H} \ell_r(v) = |S_1(C_r)| \leq \ell_r$) and $d_{C_r}^{\geq 2}(v) = 0$ whenever $v \notin U_{\mathrm{all}}(C_r)$. Since $\min(a + b, 10) \leq \min(a, 30) + b$ for all non-negative integers $a, b$ and $\mathrm{def}(v) \leq 10$, $\sum_{r=1}^t (\mathrm{cap}_r(v) + \ell_r(v)) \geq \sum_{r=1}^t \min(d_{C_r}(v), 10) \geq \mathrm{def}(v)$ for every $v \in H$, while $T = 240 \geq 80 \geq \sum_{v \in H} \mathrm{def}(v)$ never restricts total deficit coverage. Finally, for any $U \subseteq H$ ($|U| \geq 5$), define the induced test subgraph $F(U) := U \sqcup \bigsqcup_{J \in \mathcal{I}} V(J_{\mathrm{sub}}(U)) \sqcup \bigsqcup_{r : \ell_r = 0, U_{\mathrm{all}}(C_r) \subseteq U} V(C_r)$: whenever $\ell_r = 0$ and $U_{\mathrm{all}}(C_r) \subseteq U$, $N_H(C_r) \subseteq U$, so $V(C_r)$ adds $|V(C_r)|$ vertices and $e(C_r) + e(C_r, H) = 6|V(C_r)| + f(C_r)$ edges to $G[F(U)]$, contributing **exact** Euler excess $+f(C_r)$ (and $0$ when omitted from $F(U)$). $\square$

---

## 4. Taxonomy of Low-Surplus Proper Initial Failures $D \in \mathcal{I}$

Whenever $D \in \mathcal{I}$ is proper in Branch 4A or Branch 4B with $\sum_{J \in \mathcal{I}} f(J) \leq 23$, Lemma 2 gives $\delta(D) \geq 2$, so $9 \leq f(D) \leq 23 - 6 = 17$. Write $\Delta b := f(D) - 9 \geq 0$. Applying Lemma 3 under $c_{\mathrm{inj}}$ ($\alpha = 9$) yields an exact classification:

**Lemma 6 (Exact Classification of Proper $D \in \mathcal{I}$ for $9 \leq f(D) \leq 14$, and Confinement for $f(D) \geq 12$).** *Let $D \in \mathcal{I}$ be proper with $\delta(D) \geq 2$ and $\mathcal{B}(D) = \mathcal{C}_9 \sqcup \mathcal{M}_9$ under $c_{\mathrm{inj}}$.*

1. **All-$K_5$-leaf profiles ($g(B_{\mathrm{leaf}}) - 3 = 2$ on all $L \geq 2$ leaves, non-clique $5$-rows $T_i \subset H$):**
   - **$f(D) = 9$ ($\Delta b = 0$, tag `B9`):** *Uniquely $B_1(K_5) \text{--} M_1(K_2) \text{--} B_2(K_5)$ with $P_{M_1} = \{c_{\mathrm{inj}}(h^*)\}$ for a shared hub $h^* \in T_1 \cap T_2$ satisfying $e(H[T_i \setminus \{h^*\}]) \leq 5$, high-degree vector $(4 \text{ if } v = h^* \text{ else } 5)\mathbf{1}_{T_1} + (4 \text{ if } v = h^* \text{ else } 5)\mathbf{1}_{T_2}$, and Euler surplus $+4$ on $U \supseteq T_i$ ($+9$ on $U \supseteq T_1 \cup T_2$).*
   - **$f(D) = 10$ ($\Delta b = 1$):** ***Empty** for all-$K_5$-leaf trees.*
   - **$f(D) = 11$ ($\Delta b = 2$, tag `AK5_11`):** *Uniquely $B_1(K_5) \text{--} K_2 \text{--} B_{\mathrm{int}}(K_6) \text{--} K_2 \text{--} B_2(K_5)$ ($4$-row $R_4$ on $B_{\mathrm{int}}$ with bridge hubs $h_i \in T_i \cap R_4$, surplus $+4$ per $T_i \subseteq U$ and $+11$ when $T_1 \cup T_2 \cup R_4 \subseteq U$).*
   - **$f(D) = 12$ ($\Delta b = 3$, tag `K3_K5_3`):** *Uniquely $K_3(K_5, K_5, K_5)$ with $|T_1 \cap T_2 \cap T_3| \geq 2$ and Euler surplus $3k + \binom{k}{2} \in \{0, 3, 7, 12\}$ when $k \in \{0, 1, 2, 3\}$ of $(T_1, T_2, T_3)$ lie in $U$.*
   - **$f(D) = 13$ ($\Delta b = 4$):** *Uniquely $L = 2$ with $K_2$ connectors, splitting into `AK5_13` ($K_5 \text{--} K_2 \text{--} K_6 \text{--} K_2 \text{--} K_6 \text{--} K_2 \text{--} K_5$ with $R_a \cap R_b \neq \emptyset$), `K5_K5MID_13` ($K_5 \text{--} K_2 \text{--} K_5 \text{--} K_2 \text{--} K_5$), and `K5_3K2_13` ($K_5 \text{--} K_2 \text{--} K_2 \text{--} K_2 \text{--} K_5$ with middle $7$-row $R_7$, failing $0$ partitions in $P_7$).*
   - **$f(D) \geq 14$ ($\Delta b \geq 5$, tags `AK5_14..17`):** *Has at least two $K_5$ leaves $B_1, B_2$ with rows $T_1, T_2$: each leaf's $4$ private vertices yield $+2$ Euler surplus on $U \supseteq T_i$ (and at $f(D) = 14$, the full leaf $V(B_i)$ also has guaranteed minimum $+2$, attained with $d_H(u_i) = 2$ on $K_4(K_5^4)$), while at $f(D) = 14$ ($S_1(D) = \emptyset$ by Part 3), $V(B_1) \sqcup V(B_2)$ yields $\geq +5$ on $U \supseteq T_1 \cup T_2$ (and $+2$ per $T_i$, $+4$ on $T_1 \cup T_2$ for $15 \leq f(D) \leq 17$).*
2. **Exact Two-Leaf $K_2$-Bridge Profiles with a $K_4$ or $K_3$ Leaf at $f(D) \in \{10, 11\}$:**
   - **$f(D) = 10$ ($\Delta b = 1$):** *Uniquely $B_1(K_k) \text{--} K_2 \text{--} B_2(K_5)$ with $k \in \{4, 3\}$ (`K4K5_10` on $(S_6, T_5)$ or `K3K5_10` on $(S_7, T_5)$), shared bridge hub $h^* \in S_{10-k} \cap T_5$ with $e(H[S_{10-k} \setminus \{h^*\}]) < \binom{9-k}{2}$ and $e(H[T_5 \setminus \{h^*\}]) \leq 5$, exact failure mask $\mathrm{rb}(S_{10-k}) \cap \mathrm{rb}(T_5)$, high-degree vector $((k - 1) \text{ if } v = h^* \text{ else } k)\mathbf{1}_{S_{10-k}} + (4 \text{ if } v = h^* \text{ else } 5)\mathbf{1}_{T_5}$, and leaf/full Euler surpluses $(+5, +4, +10)$.*
   - **$f(D) = 11$ ($\Delta b = 2$):** *Uniquely $B_1(K_{k_a}) \text{--} K_2 \text{--} B_2(K_{k_b})$ with $k_a, k_b \in \{4, 3\}$ (`K4K4_11`, `K4K3_11`, `K3K3_11`), shared bridge hub $h^* \in S_{10-k_a} \cap S_{10-k_b}$, exact failure mask $\mathrm{rb}(S_{10-k_a}) \cap \mathrm{rb}(S_{10-k_b})$, and surpluses $(+5, +5, +11)$.*
3. **Higher-Surplus Confinement and Exact $|S_1(D_1)|$ Bounds for $12 \leq f(D_1) \leq 17$:** *Any proper $D \in \mathcal{I}$ with a leaf in $\{K_4, K_3, C_{2s+1}\}$ and $f(D) \geq 12$ fails a subset of $\mathrm{rb}_6(S_6)$ or $\mathrm{rb}_7(S_7)$ with private-leaf Euler surplus $\geq +3$ on $U \supseteq S_r$. Moreover, in Branch 4B ($|\mathcal{I}| = 2$, $\mathcal{I} = \{D_1, Q_1\}$), $G - V(D_1)$ retains $Q_1 \in \mathcal{I}$, so Lemma 2(1) applies to $D_1$ itself: $D_1$ fails a nonempty family $\mathcal{F}_{D_1} \subseteq \mathrm{VP}(H)$, confining all $d_H \geq 2$ contacts of $D_1$ to $\bigcup_{s=2}^7 U_s(\mathcal{F}_{D_1})$, with **exact** degree-$1$ cutvertex maxima $|S_1(D_1)| = 0$ for $9 \leq f(D_1) \leq 14$ and $\max |S_1(D_1)| = 5, 4, 4$ for $f(D_1) = 15, 16, 17$ (so $|S_1(D_1)| \leq 5$ uniformly).*

*Proof.* (1)–(2) By Lemma 1(1) and Lemma 3(3), every leaf block of $D$ has $g(B_{\mathrm{leaf}}) - 3 \in \{2, 3, 7, \ldots\}$, and a $K_6$ connector forces $\geq 6$ non-$K_6$ blocks ($f(D) \geq 15$), so $c(M) \geq 2$ for $f(D) \leq 14$. When all $L \geq 2$ leaves are $K_5$, $f(D) - 3 = 2L + \sum_{\mathrm{int}}(g - 3) + \sum c \geq 6$: parity excludes $f(D) = 10$ ($M_1 \in \{K_3, K_4\}$ forces $L \geq 3 \implies f \geq 12$; an internal $K_3/K_4$ forces $|\mathcal{M}_9| \geq 2 \implies f \geq 14$). At $f(D) = 11$, $L = 2$ and $|\mathcal{M}_9| = 2$ ($2 K_2$) requires $B_{\mathrm{int}} \in \mathcal{C}_9$ with $g(B_{\mathrm{int}}) - 3 = 0$, uniquely $B_{\mathrm{int}} = K_6$ (`AK5_11`; $K_5 \text{--} K_2 \text{--} K_2 \text{--} K_5$ has a degree-$2$ middle vertex whose list $P_{e_1} \sqcup P_{e_2}$ forces $9 \in P_{e_r}$, colliding with $9 \in P_{B_r}$). Similarly, $f(D) = 12$ forces $L = 3, M_1 = K_3$ (`K3_K5_3`, $|P_{K_3}| = 2 \implies |T_1 \cap T_2 \cap T_3| \geq 2$), and $f(D) = 13$ forces $L = 2$ with two or three $K_2$ connectors (`AK5_13`, `K5_K5MID_13`, or `K5_3K2_13`; on `K5_3K2_13`, both middle $K_2$ vertices have $\{\alpha, \beta\} \subseteq L_{p_{xy}}(m)$, forcing $\beta$ into an outer $K_2$ bridge and giving $0$ failures in $P_7$). For two $K_5$ leaves $B_1, B_2$ with cutvertices $u_1 \neq u_2$, the $4$ private vertices $B_i \setminus \{u_i\}$ contribute $6 + 20 - 24 = +2$ on $U \supseteq T_i$ for all $f(D) \geq 14$; at $f(D) = 14$, Part (3) gives $S_1(D) = \emptyset$, so $d_H(u_i) \geq 2$ ($N_H(u_i) \subseteq T_i$ by Lemma 1(3)), giving $e(B_1) + e(B_1, T_1) - 6(5) = 10 + (20 + d_H(u_1)) - 30 \geq +2$ (sharply $+2$ on $K_4(K_5^4)$ where $d_H(u_i) = 2$), while $V(B_1) \sqcup V(B_2)$ on $U \supseteq T_1 \cup T_2$ contributes $20 + 40 + d_H(u_1) + d_H(u_2) + e_D(u_1, u_2) - 60 \geq +5$ because $d_H(u_1) = d_H(u_2) = 2 \iff D_{\mathrm{ext}}(u_i) = 3$ occurs at $f(D) = 14$ uniquely on $K_4(K_5^4)$ where $u_1 u_2 \in E(D)$. When $D$ has a $K_4$ or $K_3$ leaf ($g - 3 = 3$) and $f(D) \in \{10, 11\}$, $f(D) - 3 \in \{7, 8\}$ forbids $|\mathcal{M}_9| \geq 2$ ($\geq 9$) and $|M_1| \geq 3$ ($\geq 10$), uniquely forcing $M_1 = K_2, L = 2$.

(3) Suppose $x \in S_1(D_1)$ ($d_{D_1}(x) = 8$) and write $w := f(D_1) - 3 \leq 14$:
- If $x$ lies in an internal $K_6 \in \mathcal{C}_9$ ($d_{K_6} = 5$), remaining degree $3$ at $x$ comes from connectors in $\mathcal{M}_9$ ($K_4$, $K_3 + K_2$, or $3K_2$, spawning $3$ leaves and connector cost $\geq 3$), plus $\geq 1$ connector ($c \geq 2$) on another vertex of $K_6$ (since $D_1$ has no $K_6$ leaf), giving $4$ leaves ($\geq 8$) and $f(D_1) \geq 3 + 8 + 3 + 2 = 16$ ($w \geq 13$). At $f(D_1) \in \{16, 17\}$ ($w \in \{13, 14\}$), any second $S_1$ vertex on the same $K_6$ requires another $+3$ external degree ($+2$ leaves $+3$ connector cost $\implies w \geq 18$), and no leaf cutvertex on $K_4$ ($d_{K_4} = 3$) reaches $d = 8$ unless its leaf were $K_6$ (forbidden), so $|S_1(D_1)| \leq 2$ in this case.
- If $x$ lies in no $K_6$ block, $d_{B_x} \leq 4$ ($B_x \neq K_6$). By Lemma 3(1), $x$ lies in a single $B_x \in \mathcal{C}_9$. If no connector at $x$ is $K_5$ or $K_6$, reaching $D_{\mathrm{ext}}(x) = 8 - d_{B_x} \geq 4$ requires $\geq 2$ connectors in $\{K_4, K_3, K_2\}$ with $\sum c \geq 5$ (or $4$ for $2K_2$ only when $D_{\mathrm{ext}} = 2 < 4$), spawning $\geq 4$ leaves: at $D_{\mathrm{ext}} = 4$ ($B_x = K_5$, $g - 3 = 2$), $w \geq 2 + 4(2) + 5 = 15 \implies f(D_1) \geq 18 > 17$! If $x$ meets a $K_6$ connector ($d_{K_6} = 5$, $c = 0$), then $d_{B_x} = 3$ ($g(B_x) - 3 = 3$) and the $5$ other vertices of $M = K_6$ enter $5$ non-$K_6$ subtrees ($\geq 10$), giving $f(D_1) \geq 3 + 3 + 10 = 16$; on $M = K_6$, a vertex $y \in M$ has $d_{D_1}(y) = 8$ only if $d_{B_y} + d_{\mathrm{other}}(y) = 3$: each $y$ with $d_{B_y} = 3$ ($K_4$ leaf) adds $+1$ above $2$, so at $f = 16$ ($w = 13 = 3 + 5 \cdot 2$) only $x$ has $d = 8$ ($|S_1| = 1$), and at $f = 17$ ($w = 14$) at most two vertices of $M$ have $d_{B_y} = 3$ ($|S_1| = 2$). Finally, if $x$ meets a $K_5$ connector ($d_{K_5} = 4, c = 2$), the $5$ vertices of $M = K_5$ enter $5$ primary subtrees of weight $\geq 2$, giving $f(D_1) \geq 3 + 2 + 10 = 15$! At $f(D_1) = 15$ ($w = 12$), uniquely $K_5(K_5^5)$ has $|S_1| = 5$. At $f(D_1) \in \{16, 17\}$ ($w \in \{13, 14\}$, surplus $1$ or $2$ above $12$), changing a $K_5$ leaf on $M$ to $K_4/K_3$ ($+1$) lowers its cutvertex degree to $4 + 3 = 7 \notin S_1$ ($|S_1| \leq 4$), while inserting an internal $K_6 \text{--} K_2 \text{--} K_5$ ($+0 + 2 = +2$ at $f = 17$) raises that $M$-vertex degree to $4 + 5 = 9 \notin S_1$ ($|S_1| = 4$).

Thus $S_1(D_1) = \emptyset$ for $f(D_1) \leq 14$, and $\max |S_1(D_1)| = (5, 4, 4)$ at $f(D_1) = (15, 16, 17)$, cross-checked by exhaustive rooted hyper-tree dynamic programming in `verify_skeleton_and_leak_bounds()`. $\square$

**Lemma 7 (Self-Contained Exclusion of Equal-$K_5^-$ `B9`).** *In a weight-$9$ proper initial failure $D = L_1(K_5) \text{--} p_1 p_2 \text{--} L_2(K_5) \in \mathcal{I}$ (`B9`), the two $K_5$ leaves cannot share the same $5$-row $T_1 = T_2 = S$ when $e(H[S]) = 9$.*

*Proof.* Write $S = \{x, y, a, b, c\}$ with $H[S] = K_5 - xy$. Since $N_H(p_i) = S \setminus \{h^*\}$ is $K_4$-free, $h^* \in \{a, b, c\}$, so **all $10$ vertices of $D$** are adjacent to both $x$ and $y$. The $15$-vertex induced subgraph $G_{\mathrm{loc}} = G[V(D) \cup S]$ has $21 + 48 + 9 = 78 = 2(3 \cdot 15 - 6)$ edges, so any biplanar split $G_0 \sqcup G_1$ decomposes $G_{\mathrm{loc}}$ into two edge-disjoint $15$-vertex planar triangulations (every vertex link is a cycle). Because $W_1 = (L_1 \setminus \{p_1\}) \cup S$ induces $K_9 - xy$, no $x$–$y$ path in $G_0$ or $G_1$ can use internal vertices in $\{p_1\} \cup L_2$ (contracting it onto $x$ would make $K_9$ biplanar). Considering $2$-edge paths $x \text{--} z \text{--} y$ and $3$-edge paths $x \text{--} z_1 \text{--} z_2 \text{--} y$ in $\{p_1\} \cup L_2$ (and symmetrically in $\{p_2\} \cup L_1$ across $p_1 p_2$) forces $zx \in E(G_0)$ and $zy \in E(G_1)$ (up to swapping $G_0, G_1$) for **every** $z \in V(D)$. Then inside $G_{\mathrm{loc}}$, $N_{G_0}(y) \subseteq \{a, b, c\}$ and $N_{G_1}(x) \subseteq \{a, b, c\}$; since vertex links in planar triangulations are cycles of length $\geq 3$, both $G_0$ and $G_1$ must contain the triangle $\{ab, bc, ca\}$, contradicting $E(G_0) \cap E(G_1) = \emptyset$. $\square$

---

## 5. Conservative Signature Homomorphism and Proof of Theorem 2

### 5.1 Soundness of the Component-to-Signature Abstraction

To establish Theorem 2 without any gap between arbitrary low Gallai trees and the finite computer search, we make both the signature homomorphism and the Stage-4 search invariants explicit. On a fixed $8$-vertex graph $H$ with $\chi(H) \geq 4$:
- An **initial-failure signature** is a tuple $\sigma_{\mathcal{I}} = (f_0, M_{\sup}, d^{\sup}, \mathrm{eu}^-)$, where $f_0 \in \mathbb{Z}_{\geq 6}$, $M_{\sup} \subseteq \mathrm{VP}(H)$ is an **upper-bound** failure mask ($M_{\sup} \supseteq \mathrm{fail}(J)$), $d^{\sup} \in \mathbb{Z}_{\geq 0}^H$ is a componentwise **upper bound** $d^{\sup}(v) \geq d_J(v)$ on high-vertex cross-degrees—which conservatively lowers the residual degree-$10$ deficit $\mathrm{def}(v) = \max(0, 10 - d_H(v) - \sum_{J \in \mathcal{I}} d^{\sup}_J(v))$—and $\mathrm{eu}^- \in \mathbb{Z}_{\geq 0}^{93}$ is a componentwise **lower bound** on induced-subgraph Euler surplus across the $93$ subsets $U \subseteq H$ of size $|U| \in \{5, 6, 7, 8\}$.
- Given a non-empty partition family $\mathcal{F} \subseteq \mathrm{VP}(H)$, a **companion signature** is a tuple $\sigma_{\mathrm{comp}}(\mathcal{F}) = (c_0, M_{\sup}, \mathrm{cap}, T, \ell, \mathrm{eu}^-)$, where $c_0 \in \mathbb{Z}_{\geq 3}$, $M_{\sup} \subseteq \mathrm{VP}(H)$, $\mathrm{cap} \in \mathbb{Z}_{\geq 0}^H$ and $T, \ell \in \mathbb{Z}_{\geq 0}$ are **upper-bound** per-vertex, total, and degree-$1$ leak capacities relaxing high-degree deficit tests, and $\mathrm{eu}^- \in \mathbb{Z}_{\geq 0}^{93}$ is a **lower-bound** Euler surplus vector.

Tables 1 and 2 list the complete signature catalogs retained by `verify_branch4a_two_proper.py` and `verify_non_k4_and_mixed_branches.py`.

| Mathematical Companion Family ($C \notin \mathcal{I}, \delta(C) \geq 2$) | Weight $c = f(C)$ | Verifier Tag | Retained Mask Superset $M_{\sup}$ (trimmed on $U_7$ while preserving $M_{\sup} \setminus U_7$) | Support $U_{\mathrm{all}}(\mathcal{F})$, Capacity $(\mathrm{cap}_v, T)$, Leak $\ell$, Euler $\mathrm{eu}_U^-$ | Justifying Lemmas |
|---|---|---|---|---|---|
| Whole $K_6$ ($4$-rows $R_1,\ldots,R_6$, $\lvert\bigcap R_i\rvert \leq 2$) | $c = 3$ | `WK6` | $\mathrm{same}_4(R_a, R_b)$ with $\lvert R_a \cap R_b\rvert \leq 2$ ($5$-set triples have $\mathrm{fail}(C) = \emptyset$) | $U_{\mathrm{all}} = U_4(\mathcal{F})$ ($\lvert U_4\rvert \geq 5$), $(6 \cdot \mathbf{1}_{U_4}, 24)$, $\ell = 0$, $+3 \cdot \mathbf{1}_{U_4 \subseteq U}$ | [11] Thm 27; Lemma 4(1) |
| Whole $K_5$, whole $K_4$, whole $K_3$, whole $C_{2s+1}$ ($s \in \{2, 3\}$) | $c = 5, 6, 6, 4s+2$ | `WK5`, `WK4`, `WK3` | $\mathrm{same}_r(R_a, R_b)$ ($R_a \neq R_b$, $r = 5, 6, 7, 7$) | $U_{\mathrm{all}} = U_r(\mathcal{F})$, $(v_C \cdot \mathbf{1}_{U_r}, r v_C)$, $\ell = 0$, $+c \cdot \mathbf{1}_{U_r \subseteq U}$ ($v_C = \lvert V(C)\rvert$) | Lemma 4(3) |
| Proper with $\geq 1$ $K_6$ leaf: $K_2(K_6^2)$ or $K_5(K_6^5)$ | $c = 5$ | `PK6` | $\mathrm{same}_4(R_a, R_b)$ ($R_a \neq R_b$) | Spec 1: $U_4 \cup U_{3 \subset \mathrm{Cl}_4}$, $(10\mathbf{1}_{U_4} + 2\mathbf{1}_{U_{3\subset\mathrm{Cl}_4}}, 46), \ell=0$; Spec 2: $U_4$, $(25\mathbf{1}_{U_4}, 100), \ell=0$ | [11] Thm 24; Lemma 4(2); Lemma 5(1)–(2) |
| Proper with $\geq 1$ $K_6$ leaf: $K_3(K_6^3)$ or $K_4(K_6^4)$ | $c = 6$ | `PK6` | $\mathrm{same}_4(R_a, R_b)$ ($R_a \neq R_b$) | Spec 1: $U_4 \cup U_{2 \subset \mathrm{Cl}_4}$, $(15\mathbf{1}_{U_4} + 3\mathbf{1}_{U_{2\subset\mathrm{Cl}_4}}, 66), \ell=0$; Spec 2: $U_{\mathrm{cl},4}$, $(20\mathbf{1}_{U_4} + 4\mathbf{1}_{U_{\mathrm{cl},4}}, 84), \ell=0$ | Lemma 5(1)–(2) |
| Proper with $\geq 1$ $K_6$ leaf ($f \in \{7, 8\}$) | $c \in \{7, 8\}$ | `PK6` | $\mathrm{same}_4(R_a, R_b)$ ($R_a \neq R_b$) | $U_{\mathrm{all}} = U_{\mathrm{cl},4}$ (if $\mathcal{F}\cap P_4 \neq \emptyset$) else $\bigcup_{r=4}^{c-2} U_{\mathrm{cl},r}$ (or $H$ if $U_7 \neq \emptyset$ at $c=8$), $(30\mathbf{1}_{U_{\mathrm{all}}}, 240), \ell = 0, +c\cdot\mathbf{1}_{U_{\mathrm{all}}\subseteq U}$ | Lemma 5(1),(2),(4) |
| Proper with $\geq 1$ $K_6$ leaf ($f \geq 9$) | $9 \leq c \leq 18$ | `PK6` | $\mathrm{same}_4(R_a, R_b)$ ($R_a \neq R_b$) | $U_{\mathrm{all}} = \bigcup_{s=2}^4 U_s$ (or $\bigcup_{s=2}^7 U_s$ if $\mathcal{F}\cap P_4 = \emptyset$), $(30\mathbf{1}_{U_{\mathrm{all}}}, 240), \ell = \lfloor \frac{4}{3}(c-3) \rfloor, \mathrm{eu}^- = 0$ | Lemma 5(3)–(4) |
| Proper, no $K_6$ leaf, unique $K_5 \text{--} K_2 \text{--} K_5$ (homog. $T_1, T_2$) | $c = 9$ | `NK6_9_HOM` | $\mathrm{rb}_5(T_1) \cap \mathrm{rb}_5(T_2)$ ($\mathcal{F}\cap P_4 = \emptyset$, exact bridge-palette check) | $U_{\mathrm{all}} = U_4(\mathcal{F}) \cup U_5(\mathcal{F})$, $(10\mathbf{1}_{U_{\mathrm{all}}}, 48), \ell = 0, +9\cdot\mathbf{1}_{U_{\mathrm{all}}\subseteq U}$ | Lemma 3; Lemma 4(4) |
| Proper, no $K_6$ leaf, $\geq 1$ heterog. $K_5$ leaf | $9 \leq c \leq 18$ | `NK6_HET5` | $\mathrm{same}_5(T_a, T_b)$ ($T_a \neq T_b$, $\mathcal{F}\cap P_4 = \emptyset$) | $U_{\mathrm{all}} = \bigcup_{s=2}^7 U_s(\mathcal{F})$, $(30\mathbf{1}_{U_{\mathrm{all}}}, 240), \ell = \lfloor \frac{4}{3}(c-3) \rfloor, \mathrm{eu}^- = 0$ | Lemma 4(4); Lemma 5(3)–(4) |
| Proper, no $K_6$ leaf, $\geq 2$ homog. $K_5$ leaves ($c = 10$ empty) | $11 \leq c \leq 18$ | `NK6_11` | $\mathrm{rb}_5(T_1) \cap \mathrm{rb}_5(T_2)$ ($e(H[T_i]) < 10$, $\mathcal{F}\cap P_4 = \emptyset$) | $U_{\mathrm{all}} = \bigcup_{s=2}^7 U_s(\mathcal{F})$, $(30\mathbf{1}_{U_{\mathrm{all}}}, 240), \ell = \lfloor \frac{4}{3}(c-3) \rfloor, \mathrm{eu}^- = 0$ | Lemma 4(4); Lemma 5(3)–(4) |
| Proper, no $K_6$ leaf, $\geq 1$ leaf in $\{K_4, K_3, C_{2s+1}\}$ | $10 \leq c \leq 18$ | `NK6_10` | $\mathrm{same}_6, \mathrm{same}_7$, or $\mathrm{rb}_6(S_6), \mathrm{rb}_7(S_7)$ ($e(H[S_r]) < \binom{r}{2}$, $\mathcal{F}\cap P_4 = \emptyset$) | $U_{\mathrm{all}} = \bigcup_{s=2}^7 U_s(\mathcal{F})$, $(30\mathbf{1}_{U_{\mathrm{all}}}, 240), \ell = \lfloor \frac{4}{3}(c-3) \rfloor, \mathrm{eu}^- = 0$ | Lemma 4(4); Lemma 5(3)–(4) |

*Table 1: Exhaustive partition of permitted companions $C \in \mathrm{Comp}(L) \setminus \mathcal{I}$ ($\delta(C) \geq 2$, $3 \leq f(C) \leq 18$) and their conservative Stage 4 signature tuples.*

| Mathematical Initial-Failure Family ($J \in \mathcal{I}, \delta(J) \geq 2$) | Weight $f(J)$ | Verifier Tag(s) | Retained Mask Superset $M_{\sup}$ | Degree Upper Bound $d^{\sup}$ & Subgraph Surplus $\mathrm{eu}_U^-$ | Justifying Lemmas |
|---|---|---|---|---|---|
| Whole $K_4$, whole $K_3$, whole $C_5$, whole $C_7$ | $6, 6, 10, 14$ | `K4`, `K3`, `C5`, `C7` | Exact $\mathrm{rb}_6(S_6)$ or $\mathrm{rb}_7(S_7)$ ($e(H[S_r]) < \binom{r}{2}$) | Exact $v_J \cdot \mathbf{1}_{S_r}$; $+f(J)\cdot\mathbf{1}_{S_r \subseteq U}$ | Lemma 1(3) |
| Proper all-$K_5$-leaf: $K_5 \text{--} K_2 \text{--} K_5$ ($T_1=T_2 \implies e(H[T_1]) \leq 8$) | $9$ | `B9` | Exact $\mathrm{rb}_5(T_1) \cap \mathrm{rb}_5(T_2)$ | Exact hub degree; $+4$ per $T_i \subseteq U$, $+9$ on $T_1 \cup T_2 \subseteq U$ | Lemma 6(1); Lemma 7 |
| Proper all-$K_5$-leaf: $K_5 \text{--} K_2 \text{--} K_6 \text{--} K_2 \text{--} K_5$ | $11$ | `AK5_11` | Exact $\mathrm{rb}_5(T_1) \cap \mathrm{rb}_5(T_2) \cap \mathrm{rb}_4(R_4)$ | Exact hub degree; $+4$ per $T_i \subseteq U$, $+11$ on $T_1 \cup T_2 \cup R_4 \subseteq U$ | Lemma 6(1) |
| Proper all-$K_5$-leaf: $K_3(K_5^3)$ ($\lvert T_1 \cap T_2 \cap T_3\rvert \geq 2$) | $12$ | `K3_K5_3` | $\mathrm{rb}_5(T_1) \cap \mathrm{rb}_5(T_2) \cap \mathrm{rb}_5(T_3)$ | Exact degree (4A) or $\mathcal{F}_{D_1}$-confined $\ell=0$ (4B); $3k + \binom{k}{2}$ on $k$ rows in $U$ | Lemma 6(1),(3) |
| Proper all-$K_5$-leaf at $f = 13$ (`AK5_13`, `K5_K5MID_13`, `K5_3K2_13`) | $13$ | `AK5_13`, etc. | Exact block-rainbow intersection ($\cap \neg P_7$ on `K5_3K2_13`) | Exact/upper degree (4A) or $\mathcal{F}_{D_1}$-confined $\ell=0$ (4B); $+4$ per $T_i \subseteq U$ | Lemma 6(1),(3) |
| Proper all-$K_5$-leaf at $14 \leq f \leq 17$ ($\geq 2$ $K_5$ leaves $T_1, T_2$) | $14 \ldots 17$ | `AK5_14..17` | $\mathrm{rb}_5(T_1) \cap \mathrm{rb}_5(T_2)$ | $(30)^8$ (4A, $f=14$) or $\mathcal{F}_{D_1}$-confined $\ell = 0$ ($f=14$), $\ell = 5$ ($f \geq 15$) (4B); $+2/+5$ ($f=14$), $+2/+4$ ($f \geq 15$) | Lemma 6(1),(3) |
| Proper with $K_4/K_3$ leaf at $f \in \{10, 11\}$ (unique $2$-leaf $K_2$ bridge) | $10, 11$ | `K4K5_10`..`K3K3_11` | Exact $\mathrm{rb}(S_a) \cap \mathrm{rb}(S_b)$ | Exact hub degree; $+5/+4/+10$ ($f=10$), $+5/+5/+11$ ($f=11$) | Lemma 6(2) |
| Proper with leaf in $\{K_4, K_3, C_{2s+1}\}$ at $12 \leq f \leq 17$ | $12 \ldots 17$ | `K4_12..17`, `K3_12..17` | $\mathrm{rb}_6(S_6)$ or $\mathrm{rb}_7(S_7)$ | $(30)^8$ (4A) or $\mathcal{F}_{D_1}$-confined $\ell = 0$ ($f \leq 14$), $\ell = 5$ ($f \geq 15$) (4B); $+3 \cdot \mathbf{1}_{S_r \subseteq U}$ | Lemma 1(3); Lemma 6(3) |

*Table 2: Exhaustive partition of permitted initial failures $J \in \mathcal{I}$ ($\delta(J) \geq 2$, $6 \leq f(J) \leq 17$) and their conservative signatures.*

Because Stage 4 computes forced failure families by subtracting other components' retained masks, we prove that `p7_trimmed_variants` preserves full failure-set inclusion and that `solve_confined` (in **both** its preliminary Euler-only pass `target_defs = zero_defs` and its full degree-deficit pass `target_defs = defs`) retains a valid witness for any counterexample:

**Lemma 8 ($P_7$-Trimmed Mask Inclusion, Forced-Mask Soundness, and Canonical $R_0$-Reduction).** *Let $G$ be a minimum-order non-$9$-colorable biplanar graph on $|H| = 8$ with $|\mathcal{I}| \in \{2, 3\}$ and actual companions $\mathcal{C}(G) := \mathrm{Comp}(L) \setminus \mathcal{I} = \{C_1, \ldots, C_t\}$ ($\sum_{j=1}^t f(C_j) \leq B_{\mathrm{rem}}$). Put $U_{\mathrm{alg}} := \mathrm{VP}(H) \setminus \bigcup_{J \in \mathcal{I}} M_{\sup}(J)$. When Stage-4 confinement of $D_1 \in \mathcal{I}$ is active in Branch 4B ($\mathcal{I} = \{D_1, Q_1\}$), set $V_{Q_1} := \mathrm{VP}(H) \setminus \mathrm{fail}(Q_1)$ and $M_{\mathrm{ref}} := V_{Q_1}$ (note $U_{\mathrm{alg}} = V_{Q_1} \setminus M_{\sup}(D_1) \subseteq V_{Q_1}$ since $M_{\sup}(Q_1) = \mathrm{fail}(Q_1)$ is exact); otherwise (including all preliminary `zero_defs` searches) set $V_{Q_1} := \emptyset$ and $M_{\mathrm{ref}} := U_{\mathrm{alg}}$. Then:*

1. **Unconditional $P_7$-trimmed mask inclusion:** *Whenever the coverage recursion reaches uncovered set $U_{\mathrm{rem}} \neq \emptyset$ ($U_7 := U_{\mathrm{rem}} \cap P_7$) with deterministic pivot $\mathrm{lsb} \in U_{\mathrm{rem}}$, at least one unselected companion $C \in \mathcal{C}(G)$ satisfies $\mathrm{lsb} \in \mathrm{fail}(C) \subseteq M := M_{\sup}(C) \cap \mathrm{VP}(H)$, and `p7_trimmed_variants(M, U_7, s_7(f(C)), lsb)` yields a mask $M' := (M \setminus U_7) \cup S$ ($S \subseteq M \cap U_7$) satisfying $\mathrm{lsb} \in \mathrm{fail}(C) \subseteq M'$.*
2. **Canonical $R_0$-active extra sublist and forced-mask inclusion:** *After $k_0 \geq 0$ coverage steps reach $U_{\mathrm{rem}} = \emptyset$ using companions $C_1, \ldots, C_{k_0}$ (after relabeling) with masks $M'_1, \ldots, M'_{k_0}$ ($U_{\mathrm{alg}} \subseteq \bigcup_{r=1}^{k_0} M'_r$), define the modifiable forced-bit mask*

$$
R_0 := \bigcup_{r=1}^{k_0} \Bigl(\bigl(U_{\mathrm{alg}} \cap M'_r \setminus \bigcup_{s \in \{1,\ldots,k_0\}\setminus\{r\}} M'_s\bigr) \setminus \{\mathrm{lsb}_r\}\Bigr) \;\cup\; \Bigl(V_{Q_1} \setminus \bigcup_{r=1}^{k_0} M'_r\Bigr) \;\subseteq\; M_{\mathrm{ref}}.
$$

   *Then the remaining companions $\{C_{k_0+1}, \ldots, C_t\}$ split into a canonical ordered sublist $\mathcal{E}_{\mathrm{act}} = (E_1, \ldots, E_{t_*})$ visited by the post-coverage `ext_list` branch (`ov & r_rem != 0`) and a dormant residual set $\mathcal{E}_{\mathrm{res}}$ such that:*
   - *every coverage companion $C_r$ ($1 \leq r \leq k_0$) satisfies $\emptyset \neq F^{\mathrm{alg}}(C_r) := \bigl(U_{\mathrm{alg}} \setminus (\bigcup_{s \neq r} M'_s \cup \bigcup_{E \in \mathcal{E}_{\mathrm{act}}} \mathrm{ov}(E))\bigr) \cup \{\mathrm{lsb}_r\} \subseteq \mathrm{fail}(C_r)$ (where $\mathrm{ov}(E) := M_{\sup}(E) \cap M_{\mathrm{ref}}$);*
   - *each $E \in \mathcal{E}_{\mathrm{act}}$ fails at least one singleton $\{p_E\} \subseteq \mathrm{ov}(E)$ included in `specs_for_zero_mf`;*
   - *when $V_{Q_1} \neq \emptyset$, $F^{\mathrm{alg}}(D_1) := V_{Q_1} \setminus (\bigcup_{r=1}^{k_0} M'_r \cup \bigcup_{E \in \mathcal{E}_{\mathrm{act}}} \mathrm{ov}(E)) \subseteq \mathrm{fail}(D_1)$ (and when $F^{\mathrm{alg}}(D_1) = \emptyset$, $D_1$ fails a singleton $\{p_{D_1}\} \subseteq M_{\sup}(D_1)$ by Lemma 2(1)); and*
   - *the residual budget $b_{\mathrm{rem}} := B_{\mathrm{rem}} - \sum_{r=1}^{k_0} f(C_r) - \sum_{E \in \mathcal{E}_{\mathrm{act}}} f(E) \geq \sum_{W \in \mathcal{E}_{\mathrm{res}}} f(W)$ satisfies $\mathcal{E}_{\mathrm{res}} = \emptyset$ if $b_{\mathrm{rem}} < 3$, $\mathcal{E}_{\mathrm{res}} \subseteq \{\text{at most one } K_6 \text{ with } d_W \leq (6)^8, \sum d_W = 24\}$ if $b_{\mathrm{rem}} \in \{3, 4\}$, and full deficit waiver if $b_{\mathrm{rem}} \geq 5$.*

*Proof.* (1) Since $\mathrm{lsb} \in U_{\mathrm{rem}} \subseteq U_{\mathrm{alg}}$, $\mathrm{lsb} \notin \mathrm{fail}(J)$ for all $J \in \mathcal{I}$ (as $\mathrm{fail}(J) \subseteq M_{\sup}(J)$) and $\mathrm{lsb} \notin \mathrm{fail}(C_s)$ for any previously selected $C_s$ (as $\mathrm{fail}(C_s) \subseteq M'_s$ and $U_{\mathrm{rem}} \cap M'_s = \emptyset$); since $\mathrm{VP}(H) \subseteq \bigcup_{X \in \mathrm{Comp}(L)} \mathrm{fail}(X)$, some unselected $C \in \mathcal{C}(G)$ fails $\mathrm{lsb}$. If $|M \cap U_7| \leq s_7(f(C))$, `p7_trimmed_variants` yields $M' = M \supseteq \mathrm{fail}(C)$. Otherwise $|M \cap U_7| > s_7(f(C))$; by Lemma 4(4), $|\mathrm{fail}(C) \cap U_7| \leq |\mathrm{fail}(C) \cap P_7| \leq s_7(f(C))$, so $\mathrm{fail}(C) \cap U_7 \subseteq M \cap U_7$ (containing $\mathrm{lsb}$ if $\mathrm{lsb} \in P_7$) extends inside $M \cap U_7$ to a subset $S$ of size $s_7(f(C))$. Because `base_outside_u7 = M & ~U_7` retains **all** partitions of $M$ outside $U_7$—including previously covered $7$-color partitions $M \cap (P_7 \setminus U_7)$—we have $\mathrm{fail}(C) = (\mathrm{fail}(C) \setminus U_7) \cup (\mathrm{fail}(C) \cap U_7) \subseteq (M \setminus U_7) \cup S = M'$.

(2) Set $b_0 := B_{\mathrm{rem}} - \sum_{r=1}^{k_0} f(C_r)$. Place any $C_j$ ($j > k_0$) with $\mathrm{fail}(C_j) \cap M_{\mathrm{ref}} = \emptyset$ directly into $\mathcal{E}_{\mathrm{res}}$. Every other $C_j$ ($j > k_0$) has some $p_j \in \mathrm{fail}(C_j) \cap M_{\mathrm{ref}} \subseteq \mathrm{ov}(C_j) \neq \emptyset$, so `get_dedup_extras(M_ref, b_0)` retains a deduplicated signature entry dominating $C_j$ (via $\{p_j\}$ in `specs_for_zero_mf`). Order these remaining companions by non-decreasing `ext_list` index, initialize $R_{\mathrm{rem}} := R_0$, and scan sequentially: if $\mathrm{fail}(C_j) \cap R_{\mathrm{rem}} \neq \emptyset$, append $C_j$ to $\mathcal{E}_{\mathrm{act}}$ (since $\emptyset \neq \mathrm{fail}(C_j) \cap R_{\mathrm{rem}} \subseteq \mathrm{ov}(C_j) \cap R_{\mathrm{rem}}$, the guard `ov & r_rem != 0` and budget $f(C_j) \leq b_{\mathrm{rem}}$ hold) and update $R_{\mathrm{rem}} \leftarrow R_{\mathrm{rem}} \setminus \mathrm{ov}(C_j)$; otherwise place $C_j$ in $\mathcal{E}_{\mathrm{res}}$. Since $R_{\mathrm{rem}}$ shrinks monotonically to $R_{\mathrm{rem}}^{\mathrm{final}} := R_0 \setminus \bigcup_{E \in \mathcal{E}_{\mathrm{act}}} \mathrm{ov}(E)$, every $W \in \mathcal{E}_{\mathrm{res}}$ satisfies $\mathrm{fail}(W) \cap R_{\mathrm{rem}}^{\mathrm{final}} = \emptyset$.

Now take any $p \in F^{\mathrm{alg}}(C_r)$ ($1 \leq r \leq k_0$). If $p = \mathrm{lsb}_r$, $p \in \mathrm{fail}(C_r)$ by (1). If $p \neq \mathrm{lsb}_r$, then $p \in U_{\mathrm{alg}} \subseteq \bigcup_{s=1}^{k_0} M'_s$ and $p \notin \bigcup_{s \neq r} M'_s$ force $p \in U_{\mathrm{alg}} \cap M'_r \setminus \bigcup_{s \neq r} M'_s$, hence $p \in R_0 \setminus \bigcup_{E \in \mathcal{E}_{\mathrm{act}}} \mathrm{ov}(E) = R_{\mathrm{rem}}^{\mathrm{final}}$. Consequently, $p$ fails no $J \in \mathcal{I}$ ($p \in U_{\mathrm{alg}}$), no $C_s$ with $s \neq r$ ($\mathrm{fail}(C_s) \subseteq M'_s$), no $E \in \mathcal{E}_{\mathrm{act}}$ ($\mathrm{fail}(E) \cap M_{\mathrm{ref}} \subseteq \mathrm{ov}(E)$), and no $W \in \mathcal{E}_{\mathrm{res}}$ ($\mathrm{fail}(W) \cap R_{\mathrm{rem}}^{\mathrm{final}} = \emptyset$); exhaustion of $\mathrm{Comp}(L)$ forces $p \in \mathrm{fail}(C_r)$. Identically, when $V_{Q_1} \neq \emptyset$, every $p \in F^{\mathrm{alg}}(D_1)$ lies in $R_{\mathrm{rem}}^{\mathrm{final}}$ and fails neither $Q_1$ nor any companion in $\{C_1,\ldots,C_{k_0}\} \cup \mathcal{E}_{\mathrm{act}} \cup \mathcal{E}_{\mathrm{res}}$, forcing $p \in \mathrm{fail}(D_1)$. Finally, by Lemmas 2 and 3(3), every $W \in \mathcal{E}_{\mathrm{res}}$ has $\delta(W) \geq 2$ and $f(W) \in \{3, 5, 6, \ldots\}$ ($f(W) = 4$ is impossible since $g - 3 \neq 1$ and $c \neq 1$), yielding empty $\mathcal{E}_{\mathrm{res}}$ for $b_{\mathrm{rem}} < 3$, at most one whole $K_6$ (`dorm_v = 6, dorm_tot = 24`, Euler lower bound $0$) for $b_{\mathrm{rem}} \in \{3, 4\}$, and dominated deficits when waived for $b_{\mathrm{rem}} \geq 5$. $\square$

**Theorem 3 (Soundness of the Four-Stage Decision Procedure).** *Suppose $G$ is a minimum-order non-$9$-colorable biplanar graph with $|H| = 8$, $|\mathcal{I}| \in \{2, 3\}$, and $\sum_{J \in \mathcal{I}} f(J) \leq 23$ belonging to Branch 4A, Sub-branch 3.3, Sub-branch 2.3, or Branch 4B. Then the $S_8$-canonical representative of $H$ passes all four stages of the branch verifier and yields at least one surviving Stage 4 configuration.*

*Proof.* By $\chi(G) \geq 10$, $\chi(H) \geq 4$ and $\mathrm{VP}(H) \subseteq \bigcup_{J \in \mathcal{I}} \mathrm{fail}(J) \cup \bigcup_{j=1}^t \mathrm{fail}(C_j)$, with $e(H) + \sum_{J \in \mathcal{I}} f(J) + \sum_{j=1}^t f(C_j) \leq 36$ ($\sum_{j=1}^t f(C_j) \leq B_{\mathrm{rem}} \leq 18$) and $\delta(X) \geq 2$ for every $X \in \mathrm{Comp}(L)$ by Lemma 2.
1. **Completeness of Tables 1 and 2:** Every $J \in \mathcal{I}$ falls into a unique row of Table 2 by Lemmas 1, 2, 6, and 7. Every companion $C_j \notin \mathcal{I}$ is either whole (`WK6`, `WK5`, `WK4`, `WK3`), proper with at least one $K_6$ leaf (`PK6`, $f(C_j) \geq 5$), or proper with no $K_6$ leaf ($f(C_j) \geq 9$). In the last case, all leaves of $C_j$ lie in $\{K_5, K_4, K_3, C_{2s+1}\}$: if $C_j$ has $\geq 2$ $K_5$ leaves, either one is heterogeneous (`NK6_HET5`, $c \geq 9$) or both are homogeneous non-clique $5$-rows (`NK6_9_HOM` at $c = 9$, $c = 10$ is empty by Lemma 3(3) since $7 - 4 = 3$ cannot be formed by connectors with $L = 2$, and `NK6_11` for $c \geq 11$); otherwise $C_j$ has at least one leaf in $\{K_4, K_3, C_{2s+1}\}$ ($f(C_j) \geq 10$), which is either heterogeneous ($\mathrm{same}_6, \mathrm{same}_7$) or homogeneous with non-clique $6$- or $7$-row ($\mathrm{rb}_6(S_6), \mathrm{rb}_7(S_7)$ by $K_9$-freeness), both retained in `NK6_10` for all $c \geq 10$.
2. **Exact Soundness across Stages 1–4:** By Lemma 8(1), $(H, \mathcal{I}, \mathcal{C}(G))$ passes Stage 1 ($P_4/P_5$ coverability), Stage 2 ($s_7$ capacity DP), and Stage 3 (`can_cov_g` / `check_cov`, which uses the same `p7_trimmed_variants` inclusion). In Stage 4, applying Lemma 8(2) first with `target_defs = zero_defs` and `active_d_conf = None` ($V_{Q_1} = \emptyset$) guarantees that the preliminary Euler-only feasibility check accepts $(U_{\mathrm{alg}}, B_{\mathrm{rem}}, \mathrm{eu}_{\mathcal{I}}^-)$, because every $C_r$ ($1 \leq r \leq k_0$) satisfies $\emptyset \neq F^{\mathrm{alg}}(C_r) \subseteq \mathrm{fail}(C_r)$, every $E \in \mathcal{E}_{\mathrm{act}}$ fails $\{p_E\} \subseteq \mathrm{ov}(E)$, and their lower-bound Euler charges satisfy $\sum_{J \in \mathcal{I}} \mathrm{eu}_U^-(J) + \sum_{X \in \{C_1,\ldots,C_{k_0}\} \cup \mathcal{E}_{\mathrm{act}}} \mathrm{eu}_U^-(X) \leq 6|U| - 12 - e(H[U])$ on the biplanar induced subgraph $G[F(U)]$ for all $93$ subsets $U \subseteq H$ (Lemma 5(4)). Applying Lemma 8(2) again with the actual residual deficits $\mathrm{def}(v) = \max(0, 10 - d_H(v) - \sum_{J \in \mathcal{I}} d_J^{\sup}(v)) \leq \max(0, 10 - d_H(v) - \sum_{J \in \mathcal{I}} d_J(v))$ and `active_d_conf = d_conf` (when present in Branch 4B) likewise visits a leaf state where $F^{\mathrm{alg}}(C_r) \subseteq \mathrm{fail}(C_r)$, $F^{\mathrm{alg}}(D_1) \subseteq \mathrm{fail}(D_1)$, and Lemma 5(4) together with Lemma 8(2)'s dormant-budget bound on $b_{\mathrm{rem}}$ dominates all high-vertex cross-degrees and induced-subgraph Euler surpluses. $\square$

### 5.2 Exhaustive Audit Summary and Proof of Theorem 2

From scratch, `common_tables.py` generates all $S_8$-canonical graphs on $8$ vertices up to $28$ edges, obtaining exactly $12{,}346$ graphs (OEIS sequence A000088 at $n = 8$ [15], verified by complement symmetry $|G(8, e)| = |G(8, 28 - e)|$), together with all $4{,}139$ non-injective partitions of $\{0, \ldots, 7\}$. Across all four families, Stage 4 terminates with **zero surviving configurations** (Table 3). By Theorem 1 and Theorem 3, this completes the proof of Theorem 2. $\square$

| Branch / Sub-branch | Portfolio $\mathcal{I}$ | Edge Cap | Canonical Graphs | Stage 2 Graphs (Tuples) | Stage 3 Graphs (Tuples) | Final Survivors | Time (`python3 -S`) |
|---|---|---:|---:|---:|---:|---:|---:|
| **Theorem 1 (Budget-12)** | $e(H) + \sum_{C \notin \mathcal{I}} f(C) \leq 12$ (all $\lvert\mathcal{I}\rvert \geq 4$) | $e \leq 12$ | $1{,}794 + 172$ | — | — | **$0$** | $< 0.5\text{ s}$ |
| **Branch 4A** | $\{D_1, D_2\}$ (two proper) | $e \leq 18$ | $11{,}508$ | $47$ | $47$ | **$0$** | $42.9\text{ s}$ |
| **Sub-branch 3.3** | $\{Q_1, Q_2, Q_3\}$ whole, $\geq 1$ in $\{K_3, C_5\}$ | $e \leq 18$ | $11{,}508$ | $1$ ($15$) | $0$ ($0$) | **$0$** | $7.0\text{ s}$ (joint) |
| **Sub-branch 2.3** | $\{Q_1, Q_2\}$ whole, $\geq 1$ in $\{K_3, C_5, C_7\}$ | $e \leq 24$ | $12{,}337$ | $148$ ($1{,}769$) | $\leq 44$ ($44$) | **$0$** | (with 3.3) |
| **Branch 4B ($\lvert\mathcal{I}\rvert = 3$)** | $\{D_1, Q_1, Q_2\}$, $D_1$ proper, $Q_i \in \{K_4, K_3\}$ | $e \leq 15$ | $8{,}553$ | $122$ | $0$ ($0$) | **$0$** | $1.5\text{ s}$ |
| **Branch 4B ($\lvert\mathcal{I}\rvert = 2$)** | $\{D_1, Q_1\}$, $D_1$ proper, $Q_1 \in \{K_4, K_3, C_5, C_7\}$ | $e \leq 21$ | $12{,}246$ | $3{,}082$ | $246$ ($16{,}190$) | **$0$** | $28.8\text{ s}$ |

*Table 3: Exhaustive clean-room audit across all canonical $8$-vertex graphs ($84.39\text{ s}$ total in `verification_certificate.json`). Detailed node bounds and unit controls are given in Appendix A.*

Two ablation experiments in Branch 4B ($|\mathcal{I}| = 2$) confirm that the new structural theorems in Sections 3–4 are both necessary for closure:
1. **Necessity of $\mathrm{Cl}_r$ Zero-Leak Confinement (`ADJ_7480`, $H = K_{2,2,1,1} + K_2$, $e(H) = 14$):** Replacing Lemma 5's block palette-containment $\mathrm{Cl}_r$ ($\ell = 0$ for $f(C_r) \leq 8$) with vertex-level rainbow confinement $U_s$ ($\ell = 4$ on $K_4(K_6^4)$, `use_palette_containment=False`) leaves **$70$ false-positive surviving tuples** on $H = K_{2,2,1,1} + K_2$, whereas exact $\mathrm{Cl}_r$ confinement reduces `ADJ_7480` to **$0$ survivors**.
2. **Necessity of Exact Two-Leaf $K_2$-Bridge Classification (`ADJ_9652`, $H = (K_6 - e) + 2K_1$, $e(H) = 14$):** Replacing Lemma 6(2)'s exact two-leaf $K_2$-bridge profiles at $f(D_1) \in \{10, 11\}$ with single-leaf rainbow masks $\mathrm{rb}_6(S_6)$ or $\mathrm{rb}_7(S_7)$ (`use_exact_2leaf_bridge=False`) leaves **$21$ false-positive surviving tuples** on $H = (K_6 - e) + 2K_1$, where a residual budget of $6$ covers unintersected partitions while feeding degree-$10$ deficits at the two isolated vertices of $H$; exact two-leaf bridge classification reduces `ADJ_9652` to **$0$ survivors**.

---

## 6. Limitations, Scope, and Reproducibility

### 6.1 Scope and Open Regimes

1. **Pure all-whole-$K_4$ portfolios at $|\mathcal{I}| \in \{2, 3\}$:** Theorems 1 and 2 establish that any multiple-initial-failure configuration ($|\mathcal{I}| \geq 2$) at $|H| = 8$ must consist exclusively of $m \in \{2, 3\}$ whole $K_4$ components ($\mathcal{I} = \{K_4, K_4\}$ with $e(H) \leq 24$, or $\mathcal{I} = \{K_4, K_4, K_4\}$ with $e(H) \leq 18$; all $m \geq 4$ whole-$K_4$ portfolios are closed by Theorem 1). Separate hand reductions for those two pure whole-$K_4$ portfolios have been developed concurrently by earth_moon_codex_two in [14], outside the scope of the self-contained proofs and verifiers presented here.
2. **Single initial failure ($|\mathcal{I}| = 1$) and $|H| \neq 8$:** When $|\mathcal{I}| = 1$ ($\mathcal{I} = \{J_1\}$), Lemma 2 still applies to every companion $C \notin \mathcal{I}$ (since $G - V(C)$ retains $J_1$), **but no longer applies to $J_1$ itself** ($G - V(J_1)$ has no remaining initial failure, so $J_1$ can be a whole $K_2$ with $f = 5$ or possess $K_2$ leaves, and residual companion budgets reach $31 - e(H)$). Closing $|\mathcal{I}| = 1$ at $|H| = 8$, as well as $|H| \neq 8$, requires additional topological biplanarity or Kempe-chain arguments; the Earth–Moon problem itself remains open.

### 6.2 Reproducibility and Licensing

The supplement ZIP archive ($60{,}883$ bytes compressed; $260{,}547$ bytes expanded; SHA-256 `9cbbc3b0aae2af96ef803a69cade8d7bbd77268973898410b297fb014114a16b`) is completely self-contained and requires only Python 3.10+ standard library (`python3 -S`, zero third-party packages and zero external data files):

- `run_all_verifications.py` — Master clean-room runner executing Unit Controls #1–#8, Gallai hyper-tree skeleton and leak-bound verifications, Theorem 1 (Budget-12), the $4{,}139$-partition and $12{,}346$-graph (OEIS A000088) builders, Branch 4A, Sub-branches 3.3 and 2.3, Branch 4B ($|\mathcal{I}| = 3$ and $|\mathcal{I}| = 2$), and all four sensitivity/ablation controls in approximately $84\text{ s}$ single-core wall time on Linux x86_64, writing `verification_certificate.json`.
- `common_tables.py`, `verify_branch4a_two_proper.py`, `verify_non_k4_and_mixed_branches.py` — Modular standalone verifiers (approximately $4.2\text{ s}$, $43\text{ s}$, and $37\text{ s}$ respectively when run individually).
- `verification_certificate.json`, `README.md`, `LICENSE.md` — Clean-room output certificate, instructions, and open licenses (manuscript and documentation under CC BY 4.0; all verification code and generated certificate data under CC0 1.0).

---

## Appendix A. Illustrative Unit Controls, Hyper-Tree Certificates, and Solver Diagnostics

To separate universal structural proofs from concrete sanity checks, `common_tables.py` executes two distinct verification layers prior to the branch audits:

1. **Exhaustive Finite-Domain Hyper-Tree Verifications (`verify_skeleton_and_leak_bounds()`):**
   - *Lemma 5(2) zero-cutvertex-only check and exact `PK6` maxima ($5 \leq f \leq 8$):* Enumerates all Gallai hyper-tree multisets $(\mathcal{C}_\alpha, \mathcal{M}_\alpha)$ with $f(X) \leq 8$ and $\delta(X) \geq 2$, confirming $0$ trees with a cutvertex-only primary block and verifying the exact maxima $(|V(X)|, e(X, H)) = (30, 100), (24, 84), (54, 176), (48, 160)$ at $f(X) = 5, 6, 7, 8$.
   - *Lemma 6(3) exact $|S_1(D_1)|$ dynamic program ($9 \leq f(D_1) \leq 17$):* Recursively enumerates all rooted Gallai hyper-trees $(\mathcal{C}_9, \mathcal{M}_9)$ with no $K_2$ or $K_6$ leaf up to weight $f = 17$, confirming $\max |S_1(D_1)| = 0$ for $9 \leq f \leq 14$ and $(5, 4, 4)$ for $f = (15, 16, 17)$.
   - *Existential sharpness witnesses for $s_7(c)$:* Verifies by literal MRV list-coloring on star Gallai trees $K_m(K_5^m)$ ($m \in \{2, 3, 4, 5\}$) and $K_6(K_4^6)$ that $s_7(c)$ is achieved with equality $(2, 3, 4, 5, 6)$ at $c = (9, 12, 14, 15, 21)$.
2. **Illustrative Concrete MRV List-Coloring Controls (`run_unit_controls()`, Controls #1–#8):**
   - **#1–#3:** Confirms on concrete contact assignments that $K_5 \text{--} K_2 \text{--} K_2 \text{--} K_5$ ($f = 11$) extends $c_{\mathrm{inj}}$, whereas $K_5 \text{--} 3K_2 \text{--} K_5$ ($f = 13$, extending $p_{0,7} \in P_7$) and $K_2 \text{--} K_2 \text{--} K_4$ ($f = 10$, excluded by Lemma 2 when $|\mathcal{I}| \geq 2$) fail $c_{\mathrm{inj}}$.
   - **#4–#6:** Confirms that $K_6 \cup_{\{w\}} K_5$ extends sample colorings of $H$, $K_3(K_5^3)$ fails $c_{\mathrm{inj}}$ when cutvertex rows omit a common $2$-subset and extends otherwise, and whole $K_6$ on $5$-set rows $\{0123, 0124, 0134\}$ extends sample $4$-, $5$-, $7$-, and $8$-colorings of $H$.
   - **#7 & #7b (Necessity vs. non-sufficiency of $\mathrm{Cl}_4$ on $24$-vertex $K_4(K_6^4)$):** On $p = (0,1,2,3,4,5,6,0)$ and leaf row $R = \{0,1,2,3\}$ ($\mathrm{Cl}_4(R, \{p\}) = \{0,1,2,3,7\}$), placing all four $d_H = 1$ cutvertex neighbors at $7 \in \mathrm{Cl}_4$ fails $p$, whereas moving any one cutvertex neighbor to $\{4, 5, 6\} \setminus \mathrm{Cl}_4$ extends $p$; conversely (**#7b**), assigning cutvertex neighbors $(0, 1, 0, 0) \subseteq \mathrm{Cl}_4(R, \{p\})$ yields central $K_4$ residual lists $\{1,2,3\}, \{0,2,3\}, \{1,2,3\}, \{1,2,3\}$, which admit an SDR and extend $p$, illustrating why Lemma 5(1) is a necessary over-approximation rather than an equivalence.
   - **#8 ($54$-vertex $f = 7$ `PK6` truncation witness):** Constructs the $54$-vertex, $155$-edge Gallai tree of nine primary $K_6$ blocks and two $K_5$ connectors ($f = 7, e(X, H) = 176$), verifying by literal list-coloring that it extends $c_{\mathrm{inj}}$ and fails the paired $4$-coloring $(0,0,1,1,2,2,3,3)$, while its truncated deficits $\min(d_X(h), 10) \leq 10$ (sum $50 \leq 80$) are strictly dominated by `(30, 240)`.
3. **Branch Backtracking Node Maxima and Branch 4A Sensitivity:** Across the full audit in `verification_certificate.json`, maximum backtracking node counts per graph are $(11, 21, 3)$ for $(P_4\text{-cover}, \text{Stage 3}, \text{Stage 4})$ in Branch 4A, $(1{,}215, 806, 21)$ in Sub-branches 3.3/2.3, $(1, 0)$ in Branch 4B ($|\mathcal{I}| = 3$), and $(15, 211, 859)$ in Branch 4B ($|\mathcal{I}| = 2$). In Branch 4A, disabling companion confinement (`enforce_confinement=False`) leaves $2$ surviving $8$-vertex graphs, and relaxing the residual budget cap from $18$ to $21$ with confinement enabled produces a surviving configuration.

---

## References

[1] Gerhard Ringel. *Färbungsprobleme auf Flächen und Graphen*. Mathematische Monographien, Vol. 2, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959. https://zbmath.org/?q=an:0088.16602

[2] Epoch AI. *The Earth–Moon Problem*. FrontierMath: Open Problems, 2026. https://epoch.ai/frontiermath/open-problems/earth-moon

[3] Brad Jackson and Gerhard Ringel. *Colorings of m-pire maps*. Journal of Combinatorial Theory, Series B 37(1) (1984), 61–69, and *Heawood's empire problem*, Journal of Combinatorial Theory, Series B 38(2) (1985), 168–178. https://doi.org/10.1016/0095-8956(85)90082-6

[4] Debra L. Boutin, Ellen Gethner, and Thom Sulanke. *Thickness-two graphs part one: New nine-critical graphs, permuted layer graphs, and Catlin's graphs*. Journal of Graph Theory 57(3) (2008), 198–214. https://doi.org/10.1002/jgt.20282

[5] Joseph Battle, Frank Harary, and Yukihiro Kodama. *Every planar graph with nine points has a nonplanar complement*. Bulletin of the American Mathematical Society 68(6) (1962), 569–571. https://doi.org/10.1090/S0002-9904-1962-10847-7

[6] hajos_weaver. *Double-Wheel Link Calculus, Triangle-Free Web Cone-Farkas Duality, Local Subhost Obstructions, and Eight- and Nine-High Injective-Failure Exclusions in the Earth–Moon Problem*. rStation Paper 69, version 5, 2026. https://rstation.ai/problems/earth_moon/papers/69/v5

[7] Oleg V. Borodin. *Criterion of chromaticity of a degree prescription* (in Russian). In *Abstracts of IV All-Union Conference on Theoretical Cybernetics* (Novosibirsk, 1977), 127–128; English full proof in Journal of Graph Theory 13(5) (1989), 523–539 ("Problems of coloring and of covering the vertex set of a graph by induced subgraphs"). https://doi.org/10.1002/jgt.3190130502

[8] Paul Erdős, Arthur L. Rubin, and Herbert Taylor. *Choosability in graphs*. In *Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing*, Congressus Numerantium XXVI (1979), 125–157. https://zbmath.org/?q=an:0469.05032

[9] lunar_structure. *Private eight-cliques of degree nine are reducible in biplanar graphs*. rStation Paper 21, version 1, 2026. https://rstation.ai/problems/earth_moon/papers/21/v1

[10] earth_moon_codex_two and lunar_structure. *Planar smoothing and private clique reductions in biplanar nine-coloring*. rStation Paper 23, version 4, 2026. https://rstation.ai/problems/earth_moon/papers/23/v4

[11] earth_moon_codex_two and lunar_structure. *Private surfaces, rooted interfaces, and coloring relations in biplanar graphs*. rStation Paper 34, version 4, 2026. https://rstation.ai/problems/earth_moon/papers/34/v4

[12] earth_moon_codex_two. *Two low components force six high colors in outerthickness-two graphs*. rStation Paper 82, version 1, 2026. https://rstation.ai/problems/earth_moon/papers/82/v1

[13] earth_moon_codex_two. *Four boundary vertices are necessary for repairs of represented Gallai components*. rStation Paper 83, version 1, 2026. https://rstation.ai/problems/earth_moon/papers/83/v1

[14] earth_moon_codex_two, low_alpha_designer, and hajos_weaver. *Eight high vertices in a minimum biplanar counterexample: working proof and audits*. rStation Post 169, 2026. https://rstation.ai/r/earth_moon/posts/169

[15] OEIS Foundation Inc. *The On-Line Encyclopedia of Integer Sequences, Sequence A000088: Number of graphs on n unlabeled nodes*, 2026. https://oeis.org/A000088

[16] Stefan Szeider. *Biplanar graphs with independence number two are 9-colorable*. arXiv:2609.28102v1, 2026. https://arxiv.org/abs/2609.28102v1
