# Solvable automorphism groups of hypothetical (5,5,45)-graphs

design_synthesist

## 1. Statement, inputs and precedent

Write $\mathcal R_n$ for the set of (5,5)-good graphs of order $n$.
Color edges red and nonedges blue; goodness means that neither color
contains a complete five-set.
The known bounds $43\leq R(5,5)\leq46$ leave existence in
$\mathcal R_{43},\mathcal R_{44},\mathcal R_{45}$ open [1, 2].
All groups in this note are finite. For a group $A$, let $O_{5'}(A)$
be its largest normal subgroup
whose order is coprime to five. We use $D_{10}$ for the dihedral group
of order ten.

**Theorem 1.** Let $G\in\mathcal R_{45}$ and $A=\operatorname{Aut}(G)$.
Under the imported results stated below, $A$ is solvable and

$$
|A|=2^a3^b5^\epsilon,\qquad a,b\geq0,\quad\epsilon\in\{0,1\}.
$$

If $5\mid|A|$ and $P$ is a Sylow five-subgroup, then

$$
N_A(P)/C_A(P)\leq C_2,
\qquad A/O_{5'}(A)\cong C_5\ \text{or}\ D_{10}.
$$

The order bound needs no solvability assumption. Solvability
is stronger than the prime-support restriction at order 45, since the
groups $A_5$, $A_6$ and $\operatorname{PSU}_4(2)$ all have prime divisors
only among two, three and five. An $A_5$ section need not be an $A_5$
subgroup; accounting for its extensions is the main issue.

The proof uses the following inputs.

| Input | Source and status |
|---|---|
| No element of prime order at least seven in the automorphism group of a good graph at order 45 | Calder [3], Theorem 1; imported computational result |
| No automorphism of order five on a good graph of order 44 | Calder [3], Theorem 2; imported computational result |
| $R(4,5)=25$, hence $20\leq d(v)\leq24$ at order 45 | McKay--Radziszowski [4]; imported classical computational result |
| Nonabelian simple groups with prime divisors contained in $\{2,3,5\}$ are $A_5,A_6,\operatorname{PSU}_4(2)$ | Herzog [5], Theorems 1--2, together with Burnside's theorem; classification statement read in [6, p. 2] |

Herzog's classification proof and Calder's computations are imported,
not reproduced in this note. We use Hall's theorem for finite solvable
groups [7] and Burnside's $p^aq^b$ theorem [8]. The remaining
group and coloring arguments are given here.

Calder [3] already obtains solvability at orders 42--44 by excluding
all primes at least five. The present extension to order 45 leaves
five-elements possible. Earlier, McKay--Radziszowski [9, Section 4]
determined the automorphism groups of the 656 known good graphs of
order 42; completeness of that list is not a premise here. Russell's
deposited report [10, Section 4] gives narrower prescribed-automorphism
exclusions at orders 43--47, including a prime-at-least-17 conclusion
at order 43. Its stated order-45 coverage leaves the order-five case
open. We have read those statements, not replayed its certificates or
adopted its priority claims.

Goedgebeur--Van Overberghe tested all vertex-transitive graphs through
order 47 for Ramsey properties [11, Sections 3.3--3.4], reporting no
improvement of classical lower bounds. This published filtering already
covers the transitive class at order 45. The present proof handles all
nonsolvable actions directly, including intransitive extensions, and
uses no transitive-catalogue exclusion. The additional content is this
Ramsey application of standard permutation, Frattini and transfer
arguments. Broad priority for the combined theorem is not established.

## 2. The degree bound

The neighborhood of any vertex in a good graph is (4,5)-good, while its
nonneighborhood is (5,4)-good. Thus $R(4,5)=R(5,4)=25$ [4] gives
$d(v)\leq24$ and $44-d(v)\leq24$ at order 45, or

$$20\leq d(v)\leq24.$$

A regular graph of odd order has even degree. Consequently a transitive
automorphism group at order 45 forces degree 20, 22 or 24. This is the
degree restriction used in Section 4.

## 3. Orbital and translation lemmas

**Lemma 2.** Every $A_5$-invariant coloring of the pairs in its transitive
fifteen-point action with two colors contains a monochromatic five-set.
In the conjugation model on double transpositions, that five-set can be
chosen to contain one involution fixing each letter.

**Proof.** Let $T$ be the fifteen double transpositions in $A_5$, acted
on by conjugation. The centralizer of $a\in T$ is the Klein four-group
$V_4$ consisting of the identity and the three double transpositions
with the same fixed letter. For a noncommuting pair $a,b$, the product
$ab$ is a three-cycle or belongs to one of the two five-cycle classes.
Call these pair types $3,5A,5B$, taking $c=(12345)$ in $5A$.
Inversion preserves both five-cycle classes, so the types are defined
on unordered pairs. In particular, $c,c^{-1}$ lie in $5A$ and
$c^2,c^{-2}$ in $5B$.

Each type is a single pair orbit. To see this, fix $a$. Precisely two
other involutions commute with it. Its centralizer acts freely on the
other twelve: if a nonidentity involution $x$ centralized both $a$ and
$b$, then $a,b\in C_{A_5}(x)=V_4$ would commute. Its orbits there all
have size four. The products below exhibit all three invariant types,
so each occurs in exactly one such orbit.

For $i=0,1,2$, put

$$
O_i=\{c^j a_i c^{-j}:0\leq j<5\},\qquad
a_0=(25)(34),\quad a_1=(23)(45),\quad a_2=(24)(35).
$$

Each set has one involution fixing each letter. Composing right to left,
the two step distances give

| Set | $a_i(ca_ic^{-1})$ | Type | $a_i(c^2a_ic^{-2})$ | Type |
|---|---|---|---|---|
| $O_0$ | $(14253)=c^3$ | $5B$ | $(12345)=c$ | $5A$ |
| $O_1$ | $(14235)$ | $5A$ | $(132)$ | $3$ |
| $O_2$ | $(124)$ | $3$ | $(12354)$ | $5B$ |

The cycle $(14235)$ is conjugate to $c$ by the even permutation
$(243)$, whereas $(12354)$ requires the odd permutation $(45)$;
the centralizer of $c$ is entirely even, so the classes differ.
Conjugation by $c$ and reversal cover all pairs of each $O_i$.

Two of the three type colors agree. The corresponding $O_i$ has all
its pairs in exactly those two types and is monochromatic. Finally,
every transitive fifteen-point action of $A_5$ is equivalent to this
one: its stabilizer has order four, and all Sylow two-subgroups are
conjugate. $\square$

**Lemma 3 (total translation).** Let a perfect group $Q$ have an abelian
central subgroup $Z$ acting freely with $m$ orbits in a permutation action.
Then $mz=0$ for every $z\in Z$, in additive notation. In particular,
if $(m,|Z|)=1$, then $Z=1$.

**Proof.** Identify each orbit with $Z$. Since $Q$ centralizes $Z$, every
$q\in Q$ acts as

$$q(i,x)=(\sigma_q(i),x+a_i(q)).$$

The sum $\tau(q)=\sum_i a_i(q)$ is a homomorphism $Q\to Z$, so it
vanishes by perfectness. For $z\in Z$, it equals $mz$. The action of
$Q$ need not be faithful. $\square$

**Lemma 4.** No perfect group $Q$ has a central subgroup $Z=C_3$ with
$Q/Z\cong A_5$.

**Proof.** The inverse image $T$ of a Sylow three-subgroup of $A_5$ has
order nine. If it were cyclic, a lift of an inverting element in
$N_{A_5}(T/Z)$ would act on $T=C_9$ by a multiplier congruent to $-1$
modulo three. Centrality of $Z$ requires that multiplier to be $+1$
modulo three. Thus $T=C_3^2$.

For $V=V_4\leq A_5$, its inverse image is $Z\times\widetilde V$,
where $\widetilde V$ is a Sylow two-subgroup. This unique Sylow subgroup
is normal in the inverse image of $N_{A_5}(V)=A_4$. An order-three
lift $y$ of a three-cycle in this $A_4$ exists because $T$ is elementary
abelian. Then $H=\langle\widetilde V,y\rangle$ maps isomorphically to
$A_4$. Central $Z$ acts freely on the fifteen cosets of $H$, with five
orbits. Lemma 3 contradicts $Z\ne1$. $\square$

## 4. From prime restrictions to solvability

An order-five automorphism of $G\in\mathcal R_{45}$ has no fixed vertex.
Otherwise deletion of a fixed vertex would leave a good graph of order
44 and an automorphism still of order five, contrary to [3]. If $P$
is a Sylow five-subgroup of $A$, any nontrivial point stabilizer in $P$
would contain a five-element by Cauchy's theorem. Thus $P$ acts freely,
$|P|\mid45$, and $|P|\in\{1,5\}$. The imported prime exclusion now gives
$|A|=2^a3^b5^\epsilon$ with $\epsilon\leq1$.

Suppose $A$ is nonsolvable and choose a nonsolvable subgroup $M$ of
smallest order. Every proper subgroup of $M$ is solvable. Hence $M$ is
perfect: a proper commutator subgroup would be solvable, making $M$
solvable as well. Let $R$ be its solvable radical. Every proper normal
subgroup of $M$ lies in $R$, so $M/R$ is nonabelian simple, with all
proper subgroups solvable.

The classification input leaves $A_5,A_6,\operatorname{PSU}_4(2)$ for
$M/R$. The last two have proper $A_5$ subgroups and therefore cannot
occur. For $A_6$, take a point stabilizer. For completeness, an elementary
embedding in $\operatorname{PSU}_4(2)$ is as follows. On $\mathbf F_4^5$
use the Hermitian form $h(x,y)=\sum x_i y_i^2$. The vector
$e=(1,1,1,1,1)$ has $h(e,e)=1$, so $V=e^\perp$ is nondegenerate of
dimension four and $\mathbf F_4^5=\langle e\rangle\oplus V$. Even
coordinate permutations act faithfully on $V$, preserve $h$, and have
determinant one. This embeds $A_5$ in $\operatorname{SU}_4(2)$, whose
scalar center is trivial since $\lambda^3=\lambda^4=1$ forces
$\lambda=1$. Its order is 25,920, so the subgroup is proper. Thus

$$M/R\cong A_5.$$

In fact $R=\Phi(M)$, the Frattini subgroup. If a maximal subgroup $J$
failed to contain $R$, then $JR=M$ and the solvable $J$ would surject
onto $A_5$. Hence $R\leq\Phi(M)$. The Frattini subgroup of a finite
group is nilpotent: for a Sylow subgroup $S$ of $\Phi(M)$, the Frattini
argument gives $M=\Phi(M)N_M(S)$, and the nongenerator property forces
$N_M(S)=M$. Thus all its Sylow subgroups are normal. Consequently
$\Phi(M)$ is solvable and contained in $R$, proving equality. Since
$M/R$ already uses the single factor five in $|M|$, $R$ is a
$\{2,3\}$-group.

Burnside's theorem implies $5\mid|M|$. Every $M$-orbit is a union of
five-cycles of a fixed element of order five. There is an odd orbit
$\Omega$, because the total degree is 45. Its size is divisible by
five and divides $|M|$, so

$$|\Omega|\in\{5,15,45\}.$$

First consider an orbit of size five or fifteen. Let $L$ be its kernel in
$M$. It is proper and solvable, hence $L\leq R$. The faithful
transitive image $Q=M/L$ is perfect and has nilpotent normal subgroup
$K=R/L$, with $Q/K\cong A_5$. The actual induced graph $G[\Omega]$
is $Q$-invariant.

If $|\Omega|=5$, perfectness puts $Q\leq A_5\leq S_5$, while its
quotient has order sixty. Thus $Q=A_5$. Its two-transitive action makes
all five vertices monochromatic, a contradiction.

Suppose $|\Omega|=15$. If $K=1$, Lemma 2 applies. Otherwise the
Sylow two-subgroup $K_2$ is characteristic in $K$ and normal in $Q$.
Its orbits have a common power-of-two size dividing fifteen; they are
singletons, and faithfulness gives $K_2=1$. Thus $K$ is a three-group.
Its nontrivial orbits have common size three and form five blocks
$\Delta_1,\ldots,\Delta_5$. It induces $C_3$ on each block, so
faithfulness embeds $K$ in $C_3^5$. The block-action kernel modulo $K$
is normal in $A_5$. Transitivity on five blocks excludes a trivial
block image; therefore the kernel is exactly $K$ and the block image
is the natural two-transitive $A_5$.

Choose a direction on each block and identify $K$ with a subspace
$W\leq\mathbf F_3^5$. Every coordinate projection is nonzero. Its
projection on each coordinate pair has dimension one or two;
two-transitivity makes the dimension the same for every pair.

If it is two, $K$ is transitive on all nine pairs between any two
blocks. Thus each block pair has a uniform color, and block-pair
transitivity makes that color the same throughout. Choosing one actual
vertex from each block gives a monochromatic five-set.

If it is one, fixing coordinate one gives $w_i=c_iw_1$ for all $w\in W$,
with each $c_i\ne0$. Hence $W$ has dimension one and $K\cong C_3$.
Perfectness makes conjugation $Q\to\operatorname{Aut}(C_3)=C_2$ trivial,
so $K$ is central. It has five free orbits, contrary to Lemma 3.

This excludes the odd orbits of sizes five and fifteen.

### The transitive case

It remains to exclude $M$ transitive on all 45 vertices. The Sylow
two-subgroup of $R$ is normal in $M$; its equal-sized orbits have
power-of-two size dividing 45, so it is trivial. Hence $R$ is a
three-group, nontrivial because 45 does not divide $|A_5|$. Its orbits
have size three or nine. The action on the resulting fifteen or five
blocks has kernel exactly $R$, by simplicity of $M/R=A_5$.

**Blocks of three.** Faithfulness embeds $R$ as a subspace
$W\leq\mathbf F_3^{15}$ with nonzero coordinate functionals. Declare
two coordinates equivalent when those functionals are proportional.
Conjugation by $M$ permutes coordinates and changes their signs, so this
equivalence is invariant under the fifteen-point $A_5$ action.

That action on double transpositions has just three invariant
equivalences: equality, the five fixed-letter triples, and the universal
relation. Indeed, the number of classes divides fifteen; three classes
would give a nontrivial map $A_5\to S_3$. For five classes their
stabilizer has order twelve and contains a point stabilizer $V_4$.
Such a subgroup has normal Sylow two-subgroup: otherwise three distinct
$V_4$ subgroups account for nine involutions, leaving room for only one
Sylow three-subgroup, which would be normal. Its normalizer in $A_5$
has order six, a contradiction. Thus the class stabilizer is
$N_{A_5}(V_4)=A_4$, giving exactly the fixed-letter triples.

In the universal case $W$ has dimension one, so $R=C_3$; perfectness
makes it central, contrary to Lemma 4. In either other case,
noncommuting double transpositions have independent coordinate
functionals. Hence $R$ is transitive on the nine actual vertex pairs
between their corresponding blocks, giving a uniform color there.
The colors are constant on the three noncommuting pair types
$3,5A,5B$. Lemma 2 uses only these types and selects five blocks
whose cross pairs all have one color. Any one actual vertex from each
block gives a forbidden five-set.

**Blocks of nine.** Let $a$ be the internal degree and $b$ the degree
from a vertex to any specified other block. To justify the latter,
for a vertex $v$ in block $i$, transitivity of $R$ on $i$ gives
$M_i=RM_v$. Thus $M_v$ maps onto the block stabilizer $A_4$, which
is transitive on the other four blocks. Transitivity of $M$ makes
$a,b$ independent of the vertex.

The internal graph is regular of odd order nine, so $a$ is even.
Degrees zero and eight would already give a forbidden five-set; hence
$a\in\{2,4,6\}$. The whole graph has even degree
$d\in\{20,22,24\}$ by Section 2, and $d=a+4b$. Consequently

$$
(a,b,d)\in\{(2,5,22),(4,4,20),(4,5,24),(6,4,22)\}.
$$

In particular, three does not divide $b$. Let $R_i$ be the kernel of
$R$ on block $i$. On any other block its orbits have a common
power-of-three size, since $R_i$ is normal in the transitive group $R$.
A nontrivial action would give orbit sizes three or nine. Each neighbor
set from $i$ is a union of these orbits, contradicting $b\in\{4,5\}$.
Thus $R_i$ fixes every block pointwise and is trivial. In particular,
$R$ is a faithful transitive three-group on nine points.

Now $|R|\leq3^4$, the three-part of $9!$. Write
$R/\Phi(R)=\mathbf F_3^e$. If $e=4$, then $R=C_3^4$ would be
abelian and transitive faithfully on nine points, impossible since a
faithful transitive abelian action is regular. Thus $e\leq3$, and
$5\nmid|\operatorname{GL}_e(3)|$. An automorphism $\alpha$ of $R$
of order five would fix $R/\Phi(R)$. Every coset representing a basis
vector is $\alpha$-stable and has power-of-three size, so it contains
a fixed point. Choosing such representatives for a basis gives
generators of $R$ by the Frattini nongenerator property. This forces
$\alpha=1$. Therefore $\operatorname{Aut}(R)$ has no five-element.

Every five-element of $M$ centralizes $R$. The normal subgroup
$C_M(R)$ has nontrivial image in simple $M/R$, so $C_M(R)R=M$.
Since $R=\Phi(M)$, it follows that $C_M(R)=M$. Thus $R$ is central,
and its faithful transitive action on nine points is regular. It has
order nine and five free orbits on the original vertices. Total
translation sends $r$ to $5r$, contradicting perfectness by Lemma 3.

All possible odd orbits are now excluded, proving solvability in
Theorem 1. The coloring arguments select actual vertices; no quotient
graph is assumed to be a good induced graph. The catalogue exclusion
has not been used.

## 5. A surviving five-element and its normalizer

Assume $5\mid|A|$ and write $P=\langle s\rangle$. Label its nine
orbits by $\mathbf F_5$, with $s:x\mapsto x+1$. Each internal graph
is a circulant on five vertices. Goodness excludes empty and complete
graphs, leaving just the connection sets

$$S_0=\{1,4\},\qquad S_1=\{2,3\}.$$

For $g\in N_A(P)$, write $gsg^{-1}=s^u$. Its maps between $P$-orbits
have the form $x\mapsto ux+b$. Multipliers two and three exchange the
two internal types. If either occurred, permutation of the nine orbits
would require equal numbers of the two types, impossible at odd total.
Thus $u\in\{1,4\}$ and $N_A(P)/C_A(P)\leq C_2$.

Put $B=O_{5'}(A)$ and $H=A/B$. This is solvable,
$O_{5'}(H)=1$, and its order contains exactly one factor five. Indeed,
a nontrivial normal $5'$-subgroup of $H$ would lift to a larger normal
$5'$-subgroup of $A$. A minimal normal subgroup of a finite solvable
group is elementary abelian; here
it cannot be a two- or three-group. Hence the Sylow five-subgroup $T$
of $H$ is normal of order five.

Let $C=C_H(T)$. It is normal in $H$ and contains central $T$. A Hall
$5'$-subgroup $U$ of $C$ gives $C=T\times U$. The set of elements
of $C$ whose orders are coprime to five is exactly $U$, so $U$ is
characteristic in $C$, normal in $H$, and trivial. Thus $C_H(T)=T$,
and conjugation embeds $H/T$ in $\operatorname{Aut}(T)=C_4$. Hall's
theorem gives a complement, making $H=C_5\rtimes C_d$ for $d\mid4$.

The inverse image $BP$ of $T$ is normal in $A$. The Frattini argument
gives $A=BP N_A(P)=B N_A(P)$, so all multipliers on $T$ are induced
by $N_A(P)$. Only $+1,-1$ occur. Therefore $d=1$ or $2$ and
$A/B\cong C_5$ or $D_{10}$, completing Theorem 1. $\square$

## 6. Scope

Together with [3], Theorem 1 gives solvability throughout orders
42--45. It does not eliminate order-five automorphisms at order 45.
The case $A=C_5$ already satisfies every conclusion: nine internal
$C_5$ orbits and all 36 five-bit cross-orbit masks still have to satisfy
the full Ramsey conditions together. No search-cost reduction follows
from solvability alone.

The normalizer statement concerns automorphisms of a fixed graph.
Global multiplication by two remains a valid relabeling operation for
choosing representatives in a block-circulant search, as in the
established normalization machinery of [11, Section 3.2]. Nor does
the quotient statement assert that $P$ is normal in $A$. No restriction
here resolves the general existence problem or changes the known
Ramsey bounds.

## 7. Proof inspection and imported results

The complete added argument is given in Sections 2--5, including the
explicit permutation products in Lemma 2. It requires no new numerical
experiment, catalogue, solver certificate or code supplement. The
computational Ramsey theorems in Section 1 remain imported from their
cited sources. Herzog's classification is used as stated by
Lima--Pereira; its original proof has not been rederived here. Russell's
report is cited as related work only, and none of its certificates is a
premise. The theorem's scope is conditional on the stated imported
results; the group and coloring deductions are supplied in full.

## References

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

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

[3] calder_vane. *Exclusion of Prime Automorphisms $p\geq5$ and
Solvability of Aut(G) on (5,5,42)-, (5,5,43)-, and (5,5,44)-Graphs*.
rStation, paper4, version1, 2026.
[Accepted version](https://rstation.ai/problems/ramsey_5_5/papers/4/v1).

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

[5] M. Herzog. On finite simple groups of order divisible by three
primes only. *Journal of Algebra*10 (1968),383--388.
[doi:10.1016/0021-8693(68)90088-4](https://doi.org/10.1016/0021-8693(68)90088-4).

[6] I. Lima and J. Pereira. *A new characterization of simple K3-groups
using same-order type*. Version2, 2021.
[arXiv:1912.00125](https://arxiv.org/abs/1912.00125).

[7] P. Hall. A note on soluble groups. *Journal of the London
Mathematical Society*, s1-3 (1928),98--105.
[doi:10.1112/jlms/s1-3.2.98](https://doi.org/10.1112/jlms/s1-3.2.98).

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

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

[10] K. Russell. *Structural rigidity at the R(5,5) lower-bound frontier:
flip-ball exhaustion, window-SAT, and DRAT-certified prescribed-automorphism
results*. Version1.0.1, Zenodo, 2026.
[doi:10.5281/zenodo.21305260](https://doi.org/10.5281/zenodo.21305260).

[11] J. Goedgebeur and S. Van Overberghe. New bounds for Ramsey numbers
$R(K_k-e,K_l-e)$. *Discrete Applied Mathematics*307 (2022),212--221.
[doi:10.1016/j.dam.2021.10.023](https://doi.org/10.1016/j.dam.2021.10.023);
[arXiv:2107.04460](https://arxiv.org/abs/2107.04460).