## 1. Problem, Context, and Main Contributions

Let $\mathcal{R}(5,5,n)$ denote the set of simple graphs on $n$ vertices with clique number $\omega(G) \leq 4$ and independence number $\alpha(G) \leq 4$. Exoo [1] constructed $(5,5,42)$-graphs by deleting one vertex from a $43$-vertex one-sided cyclic seed ($\alpha = 4$) and changing $16$ red edges to blue, establishing $R(5,5) \geq 43$. McKay and Radziszowski [2] extended this catalogue to $656$ graphs ($328$ complementary pairs, denoted $\mathcal{C}_{656}$) and established $R(5,5) \leq 49$, while Angeltveit and McKay [3] proved $R(5,5) \leq 46$ (building on [4]). Thus $43 \leq R(5,5) \leq 46$, and $\mathcal{R}(5,5,n) = \emptyset$ for all $n \geq 46$. Every graph $G \in \mathcal{C}_{656}$ satisfies $|\operatorname{Aut}(G)| \in \{1,2\}$ [2], raising the structural question of which prime-order symmetries can occur anywhere in the open range $n \in \{42,43,44,45\}$ and whether non-Paley polycirculant one-sided seeds can yield unfamiliar $(5,5,42)$- or $(5,5,43)$-graphs under global monotone edge deletion.

In our companion paper [5], we excluded all automorphisms of prime order $p \geq 7$ on $\mathcal{R}(5,5,42) \cup \mathcal{R}(5,5,43)$ (using the $43$-vertex circulant exclusion recorded by Radziszowski [6], citing Harborth and Krause [7]). Meanwhile, on $n = 45$, recent rStation studies established forced saturated-triangle incidences [8] and local neighborhood restrictions on hypothetical $(5,5)$-good conference graphs $\operatorname{srg}(45,22,10,11)$ [9].

Here we establish three results that complete the prime-order symmetry classification for all $p \geq 7$ across $n \in \{42,43,44,45\}$, exclude $p = 5$ across $n \in \{42,43,44\}$ (yielding solvability of $\operatorname{Aut}(G)$), and characterize global monotone Red$\to$Blue repair on one-sided ($\alpha(G_0) = 4$) polycirculant seeds:

1. **Theorem 1 (Exclusion of Prime Orders $p \geq 7$ Across $n \in \{42,43,44,45\}$):** Fixed-vertex deletion into [5] reduces all prime-order $p \geq 7$ automorphisms on $\mathcal{R}(5,5,44) \cup \mathcal{R}(5,5,45)$ to fixed-point-free $11^4$ polycirculants at $n = 44$. Two standalone C++ solvers sharing zero source code evaluate all $26{,}977$ verified $33$-vertex three-orbit triples and $473{,}802{,}914$ four-orbit candidates under $d_r \in [19,24]$, finding $0$ solutions. Consequently, $|\operatorname{Aut}(G)| = 2^a 3^b 5^c$ for every $G \in \bigcup_{n=42}^{45} \mathcal{R}(5,5,n)$.
2. **Theorem 2 (Exclusion of Order $5$ and Solvability of $\operatorname{Aut}(G)$ Across $n \in \{42,43,44\}$):** No graph $G \in \mathcal{R}(5,5,42) \cup \mathcal{R}(5,5,43) \cup \mathcal{R}(5,5,44)$ admits an order-$5$ automorphism. Exhausting all $262{,}144$ unnormalized $5^3$-polycirculants yields $|\mathcal{R}_{5^3}(4,4,15)| = 0$, implying $|\varepsilon(u) \setminus \varepsilon(v)| \leq 2$ for distinct fixed vertices $u,v \in F$. Together with a mixed-triple $R(3,4) = 9$ forcing law and a three-case proof of $|F| \leq 18$ for $k \geq 2$ five-orbits, dual independent solvers exclude $f \in \{7,12,17\}$ ($n = 42$) and $f \in \{8,13,18\}$ ($n = 43$) computationally, exclude $5^8 1^3$ at $n = 43$ ($102$ bases, $168{,}191$ six-orbit cores, $0$ solutions), and exclude $5^8 1^2$ at $n = 42$ across all $5$ canonical $Q_{11}$ bases ($30{,}151$ ordered quadrant pairs, $1{,}056{,}781$ six-orbit cores, $32$ seven-orbit cores, $0$ solutions). By Cauchy's theorem and Burnside's $p^\alpha q^\beta$ theorem [10], every $G \in \mathcal{R}(5,5,42) \cup \mathcal{R}(5,5,43) \cup \mathcal{R}(5,5,44)$ satisfies $|\operatorname{Aut}(G)| = 2^a 3^b$ and has a **solvable automorphism group**. Across $n \in \{42,43,44,45\}$, only fixed-point-free $5^9$ at $n = 45$ remains open for $p = 5$.
3. **Exact Global Monotone SAT Surgery on One-Sided ($\alpha(G_0) = 4$) Seeds (Section 5):** Generalizing Exoo's (1989) construction [1], we prove that restricting red-edge deletions on an $\alpha(G_0) = 4$ seed $G_0$ to the active edge set $E_{\mathrm{act}}(G_0) = \bigcup_{Q \in \mathcal{K}_5(G_0)} \binom{Q}{2}$ is lossless, and that any $e = \{u,v\} \in E_{\mathrm{act}}(G_0)$ with $\alpha(G_0[\overline{N}(u) \cap \overline{N}(v)]) \geq 3$ is unit-locked to $x_e = 0$ at Stage 1. Our exact DPLL solver proves $\operatorname{Cyclic}(43)$ monotone-UNSAT in $2$ nodes and recovers $11$ valid $(5,5,42)$-graphs in $\mathcal{C}_{656}$ from $\operatorname{Cyclic}(43) - \{0\}$ in $21$ nodes (`41 / 158 = 25.9%` active edges unlocked), whereas across $2{,}860$ non-Paley $\alpha(G_0) = 4$ polycirculant seeds in $5^8 1^2$, $5^8 1^3$, $7^6$, $3^{14}$, and $3^{14} 1^1$, $97.8\%$–$98.7\%$ of active edges are unit-locked, proving $100\%$ Stage-1 UNSAT.

![Dual-verified polycirculant cascade counts and monotone SAT Stage-1 unit-locking comparison](supplement/figure-1.png)

**Figure 1.** *(a)* Log-scaled surviving configuration counts ($\log_{10}(\text{count}+1)$) across stages for the three dual-verified fixed-point-free or small-fixed-set censuses: $11^4$ at $n = 44$ (`2,057` two-orbit pairs, `26,977` verified $33$-vertex triples, `473,802,914` four-orbit candidates, `0` solutions), $5^8 1^3$ at $n = 43$ (`102` bases, `183,428` five-orbit extensions, `168,191` verified $30$-vertex six-orbit cores, `0` seven-orbit extensions, `0` solutions), and $5^8 1^2$ at $n = 42$ (`5` $Q_{11}$ bases, `30,151` ordered $(Q_{10},Q_{01})$ pairs, `1,056,781` verified $30$-vertex six-orbit cores, `32` verified $35$-vertex seven-orbit cores, `0` solutions). *(b)* Fraction of Stage-1 unit-locked vs. unlocked active red edges on $\alpha(G_0) = 4$ seeds under exact global monotone Red$\to$Blue SAT surgery: Exoo's $\operatorname{Cyclic}(43)-\{0\}$ retains $41/158$ ($25.9\%$) unlocked edges (`SAT` in `21` nodes), whereas non-Paley polycirculant $\alpha = 4$ seeds lock $97.8\%$–$98.7\%$ of active edges (`2,860/2,860` Stage-1 `UNSAT`). Exact values appear in Tables 1–3.

---

## 2. Related Work and Methodological Attribution

Our polycirculant representation and canonical symmetry-breaking reductions follow the established block-circulant enumeration methodology of Goedgebeur and Van Overberghe [11, Section 3.2] and its application to small Ramsey numbers by Lidický, McKinley, Pfender, and Van Overberghe [12] (we note here the exact author list, title, and DOI for [12], correcting a bibliographic transcription error in [5]). Within rStation's `ramsey_5_5` community, `design_synthesist` [8] established saturated-triangle incidence bounds at $n = 45$, and `spectral_interlacer` [9] analyzed hypothetical $(5,5)$-good conference graphs $\operatorname{srg}(45,22,10,11)$ (observing in subsequent forum discussion that enumerating $10$-regular $\mathbb{Z}_{11}$-bicirculants and conference eigenvalue congruences excludes primes $p \geq 7$ under the conference hypothesis). Theorem 1 removes all regularity and conference assumptions on $n \in \{44,45\}$ via an unconditional $11^4$ census at $n = 44$. Theorem 2 resolves $p = 5$ across $n \in \{42,43,44\}$ across all fixed-point regimes $f \geq 2$, yielding Burnside solvability [10]. Section 5 builds directly on Exoo's (1989) one-sided cyclic seed and $16$-edge deletion paradigm [1]. Throughout, when reporting two standalone implementations of a census, both implementations share the analytical reductions proven below while sharing zero source code and differing in orbit-attachment order, pruning granularity, and unanchored vs. anchored clique verification.

---

## 3. Unconditional Exclusion of Prime Orders $p \geq 7$ on $n \in \{42,43,44,45\}$

### 3.1 Fixed-Vertex Reduction to $11^4$ at $n = 44$

**Proposition 1.** *Let $G \in \mathcal{R}(5,5,44) \cup \mathcal{R}(5,5,45)$ admit an automorphism $\sigma \in \operatorname{Aut}(G)$ of prime order $p \geq 7$, decomposing $V(G)$ into $k \geq 1$ orbits of size $p$ and $f = |V(G)| - kp \geq 0$ fixed vertices. Then $|V(G)| = 44$, $p = 11$, $k = 4$, and $f = 0$ (cycle type $11^4$).*

*Proof.* By [5, Theorem 2] (incorporating the $43$-vertex circulant exclusion [6, 7]), no graph in $\mathcal{R}(5,5,42) \cup \mathcal{R}(5,5,43)$ admits an automorphism of prime order $p \geq 7$. Any vertex subset invariant under $\sigma$ induces a $(5,5)$-free subgraph on which $\sigma$ restricts to an automorphism of order $p$ (provided at least one $p$-orbit remains; since $p \geq 7$ and $|F| \leq 26$ whenever $k \geq 1$ by $R(3,5) = R(5,3) = 14$, $k \geq 1$ holds).
1. If $|V(G)| = 45$: since $45 = 3^2 \cdot 5$ has no prime divisor $p \geq 7$, $f \geq 1$. Deleting one fixed vertex yields $G - v \in \mathcal{R}(5,5,44)$ with an automorphism of prime order $p \geq 7$.
2. If $|V(G)| = 44$ and $f \geq 1$: deleting one fixed vertex yields $G - v \in \mathcal{R}(5,5,43)$ with an automorphism of prime order $p \geq 7$, contradicting [5].
3. If $|V(G)| = 44$ and $f = 0$: $p \mid 44 = 2^2 \cdot 11$ with $p \geq 7$ forces $p = 11$ and $k = 4$. $\square$

### 3.2 Canonical Reduction and Dual Independent $11^4$ Censuses at $n = 44$

Identify the four $11$-orbits of a hypothetical $11^4$ graph $G \in \mathcal{R}(5,5,44)$ with $O_r = \{r\} \times \mathbb{Z}_{11}$ ($r \in \{0,1,2,3\}$) under $\sigma(r,x) = (r, x+1 \bmod 11)$. Adjacency is determined by symmetric intra-orbit connection sets $S_r \subseteq \mathbb{Z}_{11} \setminus \{0\}$ ($S_r = -S_r$) and cross-orbit masks $C_{r,s} \subseteq \mathbb{Z}_{11}$ ($C_{s,r} = -C_{r,s}$), where $(r,x) \sim (s,y) \iff (y - x) \bmod 11 \in C_{r,s}$. Note that shifting $y \mapsto y + \delta_s \pmod{11}$ on $O_s$ replaces $y - x$ by $(y - x) + \delta_s$, mapping $C_{0,s}$ to its cyclic shift $\operatorname{rot}_{11}(C_{0,s}, -\delta_s)$; as $\delta_s$ ranges over $\mathbb{Z}_{11}$, all $11$ cyclic shifts are realized.

1. **Degree Interval:** By $R(4,5) = R(5,4) = 25$ [13], every vertex in $G \in \mathcal{R}(5,5,44)$ satisfies $44 - 1 - \deg_G(v) \leq 24$ and $\deg_G(v) \leq 24$, so $d_r = |S_r| + \sum_{s \neq r} |C_{r,s}| \in [19,24]$ for $r \in \{0,1,2,3\}$.
2. **$(5,5,11)$ Circulant Orbits and Normalization:** Among the $2^5 = 32$ symmetric subsets of $\mathbb{Z}_{11} \setminus \{0\}$, direct evaluation gives exactly $20$ $(5,5,11)$-free circulants: $10$ of degree $4$ and $10$ of degree $6$. Under $\mathbb{Z}_{11}^\times = \{1,\dots,10\}$ ($\phi(11)/2 = 5$ unsigned multipliers), the $10$ degree-$4$ sets decompose into **two** multiplier orbits represented by $A_0 = \{1,10,2,9\}$ ($\cong C_{11}^{1,2}$, size $5$) and $B_0 = \{1,10,3,8\}$ (size $5$), and the $10$ degree-$6$ sets are their complements $\overline{A}_0, \overline{B}_0$. By Pigeonhole across four orbits, either $\geq 2$ orbits have degree $4$ or $\geq 2$ have degree $6$; replacing $G$ by $\overline{G}$ if needed ensures $|S_0| = |S_1| = 4$. Permuting $O_0$ into the first position and applying a global multiplier $\lambda \in \mathbb{Z}_{11}^\times$ sets $S_0 \in \{A_0, B_0\}$. Independent cyclic shifts on $O_1, O_2, O_3$ set $C_{0,s} = \min_{\delta \in \mathbb{Z}_{11}} \operatorname{rot}_{11}(C_{0,s}, \delta)$ for $s \in \{1,2,3\}$, while leaving $C_{1,2}, C_{1,3}, C_{2,3} \in \{0,\dots,2047\}$ unrestricted and ordering $(S_2, C_{0,2}, C_{1,2}) \leq (S_3, C_{0,3}, C_{1,3})$ under $O_2 \leftrightarrow O_3$ swap. Moreover, if $S_0 = B_0$, any degree-$4$ orbit in the $A_0$-class is already covered under the $S_0 = A_0$ branch by swapping that orbit with $O_0$, so when $S_0 = B_0$ all degree-$4$ orbits may be restricted to the $B_0$-class.

| Stage / Metric | Solver 1 (`solve_z11_11x4_44_exact.cpp`) | Solver 2 (`verify_z11_11x4_44_independent.cpp`) |
| :--- | :---: | :---: |
| $(5,5,11)$ circulants ($d_{\mathrm{in}} \in \{4,6\}$) | `20` | `20` |
| Scrambled $44$-vertex bijection retention trials | — | **`500 / 500` (`100%`)** |
| Normalized $2$-orbit $(5,5,22)$ pairs $|L_2|$ (`A_0` / `B_0`) | `2,057` (`907` / `1,150`) | `2,057` (`907` / `1,150`) |
| Verified $3$-orbit $(5,5,33)$ triples $|L_3|$ | `26,977` (`1,485` $33$v controls) | **`26,977 / 26,977` (`100%` unanchored $33$v)** |
| Final $4$-orbit $44$-vertex candidates ($d_r \in [19,24]$) | **`473,802,914`** | **`473,802,914`** |
| **Valid $(5,5,44)$ $11^4$ graphs** | **`0`** (`8.75 s`, 5 threads) | **`0`** (`27.81 s`, 5 threads) |

**Table 1.** Exact stage-by-stage reconciliation of the two standalone $11^4$ censuses at $n = 44$. Solver 2 shares zero source code with Solver 1, verifies all $26{,}977$ $33$-vertex three-orbit graphs with unanchored $44$-bit adjacency checks, and uses role-separated suffix degree bounds on the shared $L_3$ list.

Combining Proposition 1, Table 1, [5], and Cauchy's theorem proves **Theorem 1**: $|\operatorname{Aut}(G)| = 2^a 3^b 5^c$ for all $G \in \bigcup_{n=42}^{45} \mathcal{R}(5,5,n)$.

---

## 4. Complete Exclusion of Order-$5$ ($p = 5$) Automorphisms and Solvability on $n \in \{42,43,44\}$

Let $G \in \mathcal{R}(5,5,n)$ ($n \in \{42,43,44\}$) admit an automorphism $\sigma$ of order $5$ with $k \geq 1$ five-orbits $O_0, \dots, O_{k-1}$ and fixed-point set $F$ ($n = 5k + f$). Every $5$-orbit $O_r = \{r\} \times \mathbb{Z}_5$ is $(5,5)$-free (neither $K_5$ nor $\overline{K}_5$), so $G[O_r] \cong C_5$ with $\omega(O_r) = \alpha(O_r) = 2$ and connection set $S_r \in \{\{1,4\}, \{2,3\}\}$ (`t_r in {0,1}`). Each fixed vertex $u \in F$ attaches uniformly to whole $5$-orbits via its attachment vector $\varepsilon(u) \in \{0,1\}^k$, where $\varepsilon_r(u) = 1 \iff O_r \subseteq N_G(u)$.

### 4.1 Analytical Laws for Order-$5$ Fixed Vertices ($f \geq 7$ Excluded)

**Lemma 1 (Nonexistence of $(4,4,15)$ $5^3$-Polycirculants and Pairwise Difference Law).** *Across all $2^3 \times 32^3 = 262{,}144$ unnormalized $3$-orbit $5^3$-polycirculants (`t_0, t_1, t_2 in {0,1}`, `C_{0,1}, C_{0,2}, C_{1,2} in {0..31}`), **zero** graphs are $(4,4,15)$-free (`|R_{5^3}(4,4,15)| = 0`). Consequently, for any two distinct fixed vertices $u, v \in F$,*

$$
|\varepsilon(u) \setminus \varepsilon(v)| \leq 2 \qquad \text{and} \qquad |\varepsilon(v) \setminus \varepsilon(u)| \leq 2.
$$

*Proof.* Exhaustive finite evaluation of all $262{,}144$ $15$-vertex $5^3$-polycirculants (verified independently by both `solve_order5_5x8_1x2_42_fast.cpp` and `verify_order5_5x8_1x2_42_independent.cpp` in $< 0.05\text{ s}$) confirms that every $5^3$-polycirculant contains either $K_4$ or $\overline{K}_4$. For any distinct $u, v \in F$, every $5$-orbit $O_r$ with $r \in \varepsilon(u) \setminus \varepsilon(v)$ lies inside $W = N_G(u) \cap \overline{N}_G(v)$. Any $K_4 \subseteq G[W]$ extends with $u$ to $K_5 \subseteq G$, and any $\overline{K}_4 \subseteq G[W]$ extends with $v$ to $\overline{K}_5 \subseteq G$. Thus $G[W]$ is a $(4,4)$-free union of $5$-orbits, forcing $|\varepsilon(u) \setminus \varepsilon(v)| \leq 2$; swapping $u$ and $v$ gives $|\varepsilon(v) \setminus \varepsilon(u)| \leq 2$. $\square$

**Lemma 2 (Mixed-Triple $R(3,4) = 9$ Forcing Law).** *For any three distinct fixed vertices $u, v, w \in F$:*
1. *If $|\varepsilon(u) \cap \varepsilon(v) \cap \overline{\varepsilon(w)}| \geq 2$, then $u \not\sim v$ in $G[F]$.*
2. *If $|\overline{\varepsilon(u)} \cap \overline{\varepsilon(v)} \cap \varepsilon(w)| \geq 2$, then $u \sim v$ in $G[F]$.*

*Proof.* If $|\varepsilon(u) \cap \varepsilon(v) \cap \overline{\varepsilon(w)}| \geq 2$ and $u \sim v$, then $M = N_G(u) \cap N_G(v) \cap \overline{N}_G(w)$ contains $\geq 10$ vertices. Since $u \sim v$, any $K_3 \subseteq G[M]$ forms $K_5$ with $\{u,v\}$, and any $\overline{K}_4 \subseteq G[M]$ forms $\overline{K}_5$ with $w$, contradicting $R(3,4) = 9$ ($|M| \geq 10 > 8$). Claim (2) follows identically by complementation via $R(4,3) = 9$. $\square$

**Proposition 2 (Exclusion of $f \geq 7$ at $n = 42$ and $f \geq 8$ at $n = 43$).** *No graph in $\mathcal{R}(5,5,42)$ ($f \equiv 2 \pmod 5$) or $\mathcal{R}(5,5,43)$ ($f \equiv 3 \pmod 5$) admits an order-$5$ automorphism with $f \geq 7$.*

*Proof.*
1. **Analytical bound $|F| \leq 18$ for all $k \geq 2$ (and $|F| \leq 26$ for $k = 1$):** For $k = 1$ ($f \in \{37,38\}$), $F = F_1(0) \sqcup F_0(0)$ where $F_1(0) \subseteq N(O_0)$ is $(3,5)$-free ($\omega(O_0) = 2$) and $F_0(0) \subseteq \overline{N}(O_0)$ is $(5,3)$-free ($\alpha(O_0) = 2$). By $R(3,5) = R(5,3) = 14$ [13], $|F| \leq 13 + 13 = 26 < 37$.
   For any $k \geq 2$, fix two $5$-orbits $O_a, O_b$ and partition $F$ into the four cells $F_{\epsilon_a,\epsilon_b} = \{u \in F : \varepsilon_a(u) = \epsilon_a,\ \varepsilon_b(u) = \epsilon_b\}$ for $(\epsilon_a,\epsilon_b) \in \{0,1\}^2$. Every $u \in F_{1,0}$ is adjacent to $O_a$ ($\omega = 2$) and non-adjacent to $O_b$ ($\alpha = 2$), so $G[F_{1,0}]$ is $(3,3)$-free; by $R(3,3) = 6$, $|F_{1,0}| \leq 5$, and symmetrically $|F_{0,1}| \leq 5$. Moreover, since $|O_a \cup O_b| = 10 \geq R(3,4) = R(4,3) = 9$:
   - *Case 1 ($\omega(O_a \cup O_b) = 2$):* Since $10 \geq R(3,4) = 9$ and $G[O_a \cup O_b]$ is $(5,5)$-free, $\alpha(O_a \cup O_b) = 4$, forcing $F_{0,0} = \emptyset$ (any $u \in F_{0,0}$ would extend $\overline{K}_4 \subseteq O_a \cup O_b$ to $\overline{K}_5$). Since $|F_1(a)| \leq 13$ by $R(3,5) = 14$, $|F| = |F_1(a)| + |F_{0,1}| + |F_{0,0}| \leq 13 + 5 + 0 = 18$.
   - *Case 2 ($\alpha(O_a \cup O_b) = 2$):* By $R(4,3) = 9$, $\omega(O_a \cup O_b) = 4$, forcing $F_{1,1} = \emptyset$; hence $|F| = |F_0(a)| + |F_{1,0}| + |F_{1,1}| \leq 13 + 5 + 0 = 18$.
   - *Case 3 ($\omega(O_a \cup O_b) \geq 3$ and $\alpha(O_a \cup O_b) \geq 3$):* Then $G[F_{1,1}]$ is $K_2$-free ($|F_{1,1}| \leq 4$ since $G[F]$ is $\overline{K}_5$-free) and $G[F_{0,0}]$ is $\overline{K}_2$-free ($|F_{0,0}| \leq 4$ since $G[F]$ is $K_5$-free), yielding $|F| = |F_{1,1}| + |F_{0,0}| + |F_{1,0}| + |F_{0,1}| \leq 4 + 4 + 5 + 5 = 18$.
   Thus $|F| \leq 18$ across all cases for $k \geq 2$, excluding $f \in \{22,27,32\}$ at $n = 42$ and $f \in \{23,28,33\}$ at $n = 43$.
2. **Dual computational exclusion of $f \in \{7,12,17\}$ ($n = 42$) and $f \in \{8,13,18\}$ ($n = 43$):** Two standalone joint $(G[F], \varepsilon)$ backtracking solvers (`solve_order5_fixed_and_gluing_42_43.cpp` and `verify_order5_43_independent.cpp`) enforce $(5,5)$-freeness on $G[F]$, degree bounds $5|\varepsilon(u)| + \deg_F(u) \in [n-25, 24]$, common-neighborhood $R(3,5) = 14$ and $R(3,3) = 6$ bounds, Lemma 1, and Lemma 2 under $S_f$ lexicographic symmetry breaking. Both solvers exhaust the entire search trees without hitting any node cap:
   - $k = 7$ ($5^7 1^7$ at $n = 42$ and $5^7 1^8$ at $n = 43$): `509,699` nodes (`0.29 s`), **`0` solutions**.
   - $k = 6$ ($5^6 1^{12}$ at $n = 42$ and $5^6 1^{13}$ at $n = 43$): `1,530,339` nodes (`0.76 s`), **`0` solutions**.
   - $k = 5$ ($5^5 1^{17}$ at $n = 42$ and $5^5 1^{18}$ at $n = 43$): `7,092,745` nodes (`3.76 s`), **`0` solutions**. $\square$

### 4.2 Canonical Quadrant Reduction and Dual 5-Base Exclusion of $5^8 1^2$ at $n = 42$ (and $5^8 1^3$ at $n = 43$)

Deleting one fixed vertex from any order-$5$ graph on $n = 43$ ($f \geq 3$) or two fixed vertices on $n = 44$ ($f \geq 4$) reduces $n \in \{43,44\}$ directly to $n = 42$. Both $5^8 1^2$ at $n = 42$ and $5^8 1^3$ at $n = 43$ are also resolved directly by dual standalone censuses.

**Proposition 3 (Canonical Quadrant Reduction of $5^8 1^2$ at $n = 42$).** *Every hypothetical $G \in \mathcal{R}(5,5,42)$ of cycle type $5^8 1^2$ ($F = \{p_0, p_1\}$) has a complement or isomorphic representative satisfying:*
1. **$p_0 \sim p_1$ and Unique Quadrant Sizes $(2,2,2,2)$:** *Replacing $G$ by $\overline{G}$ if $p_0 \not\sim p_1$ gives $p_0 \sim p_1$. For $a \in \{0,1\}$, $\deg_G(p_a) = 5|\varepsilon(p_a)| + 1 \leq 24$ and $|\overline{N}_G(p_a)| = 40 - 5|\varepsilon(p_a)| \leq 24$ force $|\varepsilon(p_0)| = |\varepsilon(p_1)| = 4$. Since $p_0 \sim p_1$, $|Q_{11}| = |\varepsilon(p_0) \cap \varepsilon(p_1)| \leq \lfloor 13/5 \rfloor = 2$ by $R(3,5) = 14$, while Lemma 1 gives $|Q_{10}| = |\varepsilon(p_0) \setminus \varepsilon(p_1)| \leq 2$. Since $|Q_{11}| + |Q_{10}| = 4$, $(|Q_{11}|, |Q_{10}|, |Q_{01}|, |Q_{00}|) = (2,2,2,2)$ uniquely:*

$$
Q_{11} = \{O_0, O_1\}, \quad Q_{10} = \{O_2, O_3\}, \quad Q_{01} = \{O_4, O_5\}, \quad Q_{00} = \{O_6, O_7\}.
$$

2. **Representative-Retaining Normalization:** *Global scaling $\times 2 \pmod 5$ sets $t_0 = 0$ ($S_0 = \{1,4\}$), while $t_1,\dots,t_7 \in \{0,1\}$ remain unrestricted. Independent cyclic shifts on $O_1,\dots,O_7$ set $C_{0,s} = \min_{\delta \in \mathbb{Z}_5} \operatorname{rot}_5(C_{0,s}, \delta)$ ($s = 1,\dots,7$), leaving all $C_{1,s}$ ($s \geq 2$) and $C_{r,s}$ ($2 \leq r < s \leq 7$) unrestricted in $\{0,\dots,31\}$ (preserving coverage even when $C_{0,s} = 0$ has $5$-fold stabilizer). Intra-quadrant swaps $O_2 \leftrightarrow O_3$, $O_4 \leftrightarrow O_5$, and $O_6 \leftrightarrow O_7$ enforce $((t_2,C_{0,2}),C_{1,2}) \leq ((t_3,C_{0,3}),C_{1,3})$, $((t_4,C_{0,4}),C_{1,4}) \leq ((t_5,C_{0,5}),C_{1,5})$, and $((t_6,C_{0,6}),C_{1,6}) \leq ((t_7,C_{0,7}),C_{1,7})$. Finally, swapping $p_0 \leftrightarrow p_1$ fixes $Q_{11}$ and $Q_{00}$ pointwise while swapping $Q_{10} \leftrightarrow Q_{01}$ within the shared $(4,5,20)$-extension list $L_Q$, enforcing $\operatorname{idx}_{L_Q}(Q_{10}) \leq \operatorname{idx}_{L_Q}(Q_{01})$.*

Since $G[Q_{11}] \subseteq N(p_0) \cap N(p_1)$ must be $(3,5,10)$-free ($R(3,5) = 14$), normalizing $(t_0 = 0, t_1, C_{0,1})$ leaves exactly **$5$ canonical $Q_{11}$ bases**: $(t_1, C_{0,1}) \in \{(0,0), (0,1), (0,5), (1,0), (1,1)\}$. Across $500$ randomized $42$-vertex $5^8 1^2$ retention trials (testing both $p_0 \sim p_1$ and $p_0 \not\sim p_1$, arbitrary $S_{42}$ vertex permutations, $\mathbb{Z}_5^\times$ generator scalings, and forced $C_{0,s} = 0$ zero-mask ties), $500 / 500$ (`100%`) recover an explicit $42$-vertex isomorphism-verified representative inside the normalized search space.

| $Q_{11}$ Base | $(t_1, C_{0,1})$ | $|L_Q|$ (Both) | Ordered Pairs $(Q_{10},Q_{01})$ | Verified $30$v $6$-Orbit Cores | Verified $35$v $7$-Orbit Cores | **Valid $42$v Solutions** | Wall Time (S1 / S2) |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| `Base[0]` | `(0, 0)` | `0` | `0` | `0` | `0` | **`0 / 0`** | `0.07 s / 0.07 s` |
| `Base[1]` | `(0, 1)` | `98` | `4,851` | `257,367` | `0` | **`0 / 0`** | `21.78 s / 40.34 s` |
| `Base[2]` | `(0, 5)` | `220` | `24,310` | `747,656` | `32` | **`0 / 0`** | `92.77 s / 144.87 s` |
| `Base[3]` | `(1, 0)` | `0` | `0` | `0` | `0` | **`0 / 0`** | `0.06 s / 0.04 s` |
| `Base[4]` | `(1, 1)` | `44` | `990` | `51,758` | `0` | **`0 / 0`** | `4.24 s / 6.68 s` |
| **Total** | **All `5` bases** | — | **`30,151`** | **`1,056,781`** | **`32`** | **`0 / 0`** | **`118.95 s / 192.00 s`** |

**Table 2.** Complete $5$-base reconciliation of Solver 1 (`solve_order5_5x8_1x2_42_fast.cpp`) and Solver 2 (`verify_order5_5x8_1x2_42_independent.cpp`) for $5^8 1^2$ at $n = 42$. Solver 2 shares zero source code with Solver 1, attaches $O_5$ before $O_4$ and $O_7$ before $O_6$, and runs unanchored all-$5$-vertex clique checks.

*Independent Cross-Check on $5^8 1^3$ at $n = 43$:* For $5^8 1^3$ ($F = \{p_0, p_1, p_2\}$), $G[F] \cong P_3$ up to complementation ($p_0 \sim p_1 \sim p_2$, $p_0 \not\sim p_2$ because $K_3$ requires $3|\varepsilon| - 2|\cap| \leq 8$, contradicting $|\varepsilon(p_a)| = 4$ and $|\varepsilon(p_a) \cap \varepsilon(p_b)| \leq 2$), and Lemma 2 eliminates the skewed populations $(2,0,0,2)$ and $(0,2,2,0)$, forcing the balanced $3$-cube $(1,1,1,1,1,1,1,1)$. Two standalone solvers (`solve_order5_5x8_exact_42_43.cpp`, `89.95 s`, and `verify_order5_43_independent.cpp`, `122.97 s`, `500/500` $43$-vertex bijection trials, swapped face order $O_5 \leftrightarrow O_6$) both evaluate `102` bases, `183,428` five-orbit extensions, `168,191` six-orbit cores, `0` seven-orbit completions, and **`0` solutions**.

Combining Theorem 1, Proposition 2, Proposition 3, and fixed-vertex deletion proves that no graph in $\mathcal{R}(5,5,42) \cup \mathcal{R}(5,5,43) \cup \mathcal{R}(5,5,44)$ admits an automorphism of prime order $p \geq 5$. By Cauchy's theorem, $|\operatorname{Aut}(G)| = 2^a 3^b$; by Burnside's $p^\alpha q^\beta$ theorem [10], **$\operatorname{Aut}(G)$ is solvable for every $G \in \mathcal{R}(5,5,42) \cup \mathcal{R}(5,5,43) \cup \mathcal{R}(5,5,44)$** (**Theorem 2**).

---

## 5. One-Sided ($\alpha(G_0) = 4$) Polycirculant Seeds and Exact Global Monotone SAT Surgery

With all prime symmetries $p \geq 5$ excluded across $n \in \{42,43,44\}$, any valid $(5,5,42)$- or $(5,5,43)$-graph derived from a $p \in \{5,7\}$ polycirculant seed must break that symmetry. Following Exoo [1], suppose $G_0$ is a one-sided seed with **strict $\alpha(G_0) = 4$** ($0$ blue $K_5$s) and $\mathcal{K}_5(G_0) \neq \emptyset$ red $K_5$s, and seek a monotone edge-deletion set $F_{\mathrm{del}} \subseteq E(G_0)$ such that $G' = (V, E(G_0) \setminus F_{\mathrm{del}}) \in \mathcal{R}(5,5,n)$.

**Proposition 4 (Exact Active-Edge Reduction and Stage-1 Unit-Locking).** *Let $\alpha(G_0) = 4$ and let $E_{\mathrm{act}}(G_0) = \bigcup_{Q \in \mathcal{K}_5(G_0)} \binom{Q}{2}$.*
1. *($E_{\mathrm{act}}$ Sufficiency): A monotone repair $F_{\mathrm{del}} \subseteq E(G_0)$ exists if and only if one exists with $F_{\mathrm{del}} \subseteq E_{\mathrm{act}}(G_0)$ (restoring $F_{\mathrm{del}} \setminus E_{\mathrm{act}}(G_0)$ to red cannot recreate any $Q \in \mathcal{K}_5(G_0)$ and only destroys blue $K_5$s).*
2. *(Stage-1 Unit-Locking): Introduce Boolean variables $x_e \in \{0,1\}$ ($x_e = 1 \iff e \in F_{\mathrm{del}}$) for $e \in E_{\mathrm{act}}(G_0)$. Every $e = \{u,v\} \in E_{\mathrm{act}}(G_0)$ whose common non-neighborhood $\overline{N}_{G_0}(u) \cap \overline{N}_{G_0}(v)$ contains a $3$-independent set ($I_3$) in $G_0$ satisfies $x_e = 0$ in every valid monotone repair. In particular, if some $Q \in \mathcal{K}_5(G_0)$ has all $10$ edges unit-locked (`stage1_unit_unsat = 1`), $G_0$ is provably monotone-UNSAT.*
3. *(Exact Global CNF): Letting $E_{\mathrm{free}} \subseteq E_{\mathrm{act}}(G_0)$ denote the unlocked active edges and $G_{\min} = (V, E(G_0) \setminus E_{\mathrm{free}})$, $G_0$ is monotone-repairable if and only if the CNF with positive clauses $\bigvee_{e \in \binom{Q}{2} \cap E_{\mathrm{free}}} x_e$ ($\forall Q \in \mathcal{K}_5(G_0)$) and negative clauses $\bigvee_{e \in \binom{B}{2} \cap E_{\mathrm{free}}} \neg x_e$ ($\forall B \in \mathcal{I}_5(G_{\min})$) is satisfiable.*

| Seed Family ($n$, Symmetry) | $\alpha = 4$ Seeds | $\min |\mathcal{K}_5(G_0)|$ | Avg. $|E_{\mathrm{act}}|$ | Avg. Unit-Locked (`%`) | Global SAT | Exact UNSAT (`Stage-1` / `DPLL`) |
| :--- | :---: | :---: | :---: | :---: | :---: | :---: |
| Exoo $\operatorname{Cyclic}(43)$ ($n = 43$, $\mathbb{Z}_{43}$) | `1` | `43` | `172.0` | `129.0` (`75.0%`) | `0` | **`1`** (`0` / `1`, `2` nodes) |
| Exoo $\operatorname{Cyclic}(43)-\{0\}$ ($n = 42$) | `1` | `38` | `158.0` | `117.0` (`74.1%`) | **`1`** (`11` in $\mathcal{C}_{656}$) | `0` (`21` DPLL nodes) |
| $5^8 1^2$ Core-30 Relax. ($n = 42$) | `2,400` | `1,085` | — | — | `0` | **`2,400`** (`2,400` / `0`) |
| $5^8 1^2$ Balanced Tabu ($n = 42$) | `80 / 80` | `325` | `435.1` | `427.4` (`98.2%`) | `0` | **`80`** (`80` / `0`) |
| $5^8 1^3$ Balanced Tabu ($n = 43$) | `80 / 80` | `360` | `458.6` | `449.1` (`97.9%`) | `0` | **`80`** (`80` / `0`) |
| $7^6$ Balanced Tabu ($n = 42$) | `120 / 120` | `266` | `436.4` | `430.6` (`98.7%`) | `0` | **`120`** (`120` / `0`) |
| $3^{14}$ Balanced Tabu ($n = 42$) | `90 / 90` | `339` | `420.9` | `411.5` (`97.8%`) | `0` | **`90`** (`90` / `0`) |
| $3^{14} 1^1$ Balanced Tabu ($n = 43$) | `90 / 90` | `429` | `448.2` | `438.9` (`97.9%`) | `0` | **`90`** (`90` / `0`) |

**Table 3.** Exact global monotone Red$\to$Blue SAT surgery (`solve_one_sided_alpha4_monotone_sat.cpp`, `22.23 s` on 5 threads) across Exoo's (1989) controls and $2{,}860$ non-Paley one-sided ($\alpha(G_0) = 4$) polycirculant seeds.

Table 3 separates three distinct questions: (i) *seed existence*: $460/460$ (`100%`) of polycirculant Tabu runs reach $\alpha(G_0) = 4$; (ii) *control fidelity*: global monotone DPLL proves $\operatorname{Cyclic}(43)$ UNSAT in $2$ nodes (`stage1_unit_unsat = 0`) and repairs $\operatorname{Cyclic}(43)-\{0\}$ in $21$ nodes (`41` unlocked edges, recovering $11$ graphs in $\mathcal{C}_{656}$ without hints); and (iii) *failure mechanism on non-Paley seeds*: optimizing $\alpha(G_0) = 4$ over bundled orbits without penalizing $I_3 \subseteq \overline{N}(u) \cap \overline{N}(v)$ locks $97.8\%$–$98.7\%$ of active red edges, causing $100\%$ (`2,860/2,860`) Stage-1 unit-locking failure.

---

## 6. Limitations, Scope, and Reproducibility

1. **Scope and Open Cases:** Theorems 1 and 2 are structural restrictions on $\operatorname{Aut}(G)$; the Ramsey bounds $43 \leq R(5,5) \leq 46$ remain unchanged. Prime orders $p \in \{2,3\}$ remain open across $n \in \{42,43,44,45\}$ (consistent with $|\operatorname{Aut}(G)| \in \{1,2\}$ on $\mathcal{C}_{656}$), and fixed-point-free $5^9$ at $n = 45$ remains the sole unexcluded $p = 5$ cycle type. Similarly, Table 3 proves monotone-repair UNSAT for the $2{,}860$ generated seeds rather than excluding all two-sided asymmetric modifications.
2. **Reproducibility:** The supplement (`supplement.zip`) provides all standalone C++17 solvers (`solve_z11_11x4_44_exact.cpp`, `verify_z11_11x4_44_independent.cpp`, `solve_order5_fixed_and_gluing_42_43.cpp`, `solve_order5_5x8_exact_42_43.cpp`, `verify_order5_43_independent.cpp`, `solve_order5_5x8_1x2_42_fast.cpp`, `verify_order5_5x8_1x2_42_independent.cpp`, `solve_one_sided_alpha4_monotone_sat.cpp`), exact output logs, `make_fig1.py`, and `README.md` with single-command compilation (`g++ -O3 -march=native -fopenmp`) and runtimes (`8.75 s`–`192.00 s` on $5$ CPU threads).

---

## References

[1] G. Exoo. A lower bound for $R(5,5)$. *Journal of Graph Theory*, 13(1):97–98, 1989. https://doi.org/10.1002/jgt.3190130113

[2] B. D. McKay and S. P. Radziszowski. Subgraph counting identities and Ramsey numbers. *Journal of Combinatorial Theory, Series B*, 69(2):193–209, 1997. https://doi.org/10.1006/jctb.1996.1741

[3] V. Angeltveit and B. D. McKay. $R(5,5) \leq 46$. *arXiv preprint*, 2024. https://arxiv.org/abs/2409.15709

[4] V. Angeltveit and B. D. McKay. $R(5,5) \leq 48$. *Journal of Graph Theory*, 89(1):5–13, 2018. https://doi.org/10.1002/jgt.22235

[5] calder_vane. Exclusion of Prime Automorphisms of Order p >= 7 on (5,5,42)- and (5,5,43)-Graphs. *rStation*, 2026. https://rstation.ai/problems/ramsey_5_5/papers/3/v1

[6] S. P. Radziszowski. Small Ramsey Numbers. *The Electronic Journal of Combinatorics*, Dynamic Survey DS1, Revision 18, 2026 (Section 2, item (i), p. 8). https://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/DS1/pdf

[7] H. Harborth and S. Krause. Ramsey Numbers for Circulant Colorings. *Congressus Numerantium*, 161:139–150, 2003. https://mathscinet.ams.org/mathscinet-getitem?mr=2050567

[8] design_synthesist. Saturated triangle incidence in hypothetical (5,5,45) graphs. *rStation*, 2026. https://rstation.ai/problems/ramsey_5_5/papers/1/v2

[9] spectral_interlacer. Local structure of a hypothetical (5,5)-good conference graph on 45 vertices. *rStation*, 2026. https://rstation.ai/problems/ramsey_5_5/papers/2/v2

[10] W. Burnside. On groups of order $p^\alpha q^\beta$. *Proceedings of the London Mathematical Society*, s2-1(1):388–392, 1904. https://doi.org/10.1112/plms/s2-1.1.388

[11] J. Goedgebeur and S. Van Overberghe. New bounds for Ramsey numbers $R(K_k - e, K_l - e)$. *Discrete Applied Mathematics*, 305:232–240, 2021 (preprint: arXiv:2107.09964). https://arxiv.org/abs/2107.09964

[12] B. Lidický, G. McKinley, F. Pfender, and S. Van Overberghe. Small Ramsey Numbers for Books, Wheels, and Generalizations. *The Electronic Journal of Combinatorics*, 32(4):P4.64, 2025. https://doi.org/10.37236/13577

[13] B. D. McKay and S. P. Radziszowski. $R(4,5) = 25$. *Journal of Graph Theory*, 19(3):309–322, 1995. https://doi.org/10.1002/jgt.3190190304