Suppose a graph \(G\) on 43 vertices contains neither a \(K_5\) nor an independent set of size five. Then two rather tempting kinds of structure are already unavailable:
$$ \boxed{\text{\(G\) has no nontrivial proper module}} $$
and
$$ \boxed{\text{\(G\) is neither \(18\)-regular nor \(24\)-regular.}} $$
The first statement says the graph is prime under modular decomposition. The second knocks out the two regular endpoints of the elementary degree window
$$ 18\le d(v)\le24. $$
It does not rule out regular degree \(19,20,21,22,\) or \(23\). I want that boundary visible because the two theorems are already lovely without asking them to prove more than they do.
They also arrive by completely different routes. One is a tiny Ramsey capacity table. The other is an exact local subgraph identity that gets squeezed between \(888\) and \(936\). I keep staring at that gap.
A module cannot carry enough vertices#
A module \(M\) is a vertex set that every outside vertex sees uniformly: each outside vertex is either adjacent to all of \(M\) or to none of it. Write
$$ m=|M|, $$
$$ c=\omega(G[M]), \qquad a=\alpha(G[M]). $$
Partition the outside vertices into \(A\), complete to \(M\), and \(B\), anticomplete to \(M\). If \(A\) contained a clique of order \(5-c\), it would join a maximum clique in \(M\) to make a \(K_5\). Similarly, an independent set of order \(5-a\) in \(B\) would join one in \(M\). Therefore
$$ |A|\le R(5-c,5)-1, $$
$$ |B|\le R(5,5-a)-1. $$
The exact small Ramsey values give the outside capacities
$$ \begin{array}{c|rrrr} c\text{ or }a&1&2&3&4\\ \hline \text{capacity}&24&13&4&0. \end{array} $$
Now enumerate the possible pairs \((c,a)\) for a module of order \(m\). For \(m=2,3,4,5\), the largest possible whole-graph orders are respectively \(39,31,30,31\). The remaining ranges give
- \(m+17\) for \(6\le m\le8\);
- \(m+13\) for \(9\le m\le13\);
- \(m+8\) for \(14\le m\le17\);
- \(m+4\) for \(18\le m\le24\).
Every entry is at most \(39\). A nontrivial module therefore cannot occur in a graph of order \(40\) or more.
There is a neat hard stop at \(m=25\). Since \(R(4,5)=25\), a module that large contains both a \(K_4\) and an independent four-set. Its outside capacities are then both zero: no outside vertex may be complete or anticomplete to it. But a module requires every outside vertex to be one or the other. So a proper module of size at least \(25\) is impossible too.
Hence every \((5,5)\)-good graph of order at least \(40\) is prime. At order 43 this immediately forbids twins, disconnectedness, disconnected complement, and any automorphism whose only moved orbit is one nontrivial cycle. The number \(39\) is doing a surprising amount of work.
The lower regular endpoint creates an exact local equation#
Assume next that \(G\) is \(18\)-regular. Then
$$ e(G)=\frac{43\cdot18}{2}=387. $$
At a vertex \(v\), let \(P\) be the graph induced by its 18 neighbors and \(Q\) the graph induced by its 24 nonneighbors. Put
$$ p=e(P),\qquad q=e(Q). $$
Partition double counting gives
$$ q-p=63, $$
and the exact edge ranges for the relevant smaller Ramsey graphs force
$$ 81\le p\le85. $$
The complement \(H=\overline Q\) is a \(24\)-vertex graph with no \(K_4\) and no independent set of size five. Moreover,
$$ e(H)=\binom{24}{2}-q=213-p, $$
so \(128\le e(H)\le132\).
The complete catalogue in those five edge classes contains exactly
$$ 843+147+32+3+2=1027 $$
graphs. Direct enumeration shows that every corresponding \(Q\) has at most 296 triangles. Thus the local left side of the exact \(m=3\) subgraph-counting identity satisfies
$$ 3t(Q)\le3\cdot296=888. $$
That is one jaw of the trap.
Mantel pushes the other side past 936#
Let the internal degrees of \(P\) be
$$ a_1,\ldots,a_{18}. $$
Because \(P\) is \(K_4\)-free, the neighborhood of each vertex in \(P\) is triangle-free. Mantel's theorem therefore gives
$$ 3t(P)\le\sum_{i=1}^{18}\left\lfloor\frac{a_i^2}{4}\right\rfloor. $$
Also
$$ \sum_i a_i=2p,\qquad 0\le a_i\le13, $$
and the induced two-edge path count is
$$ p_3(P)=\sum_i\binom{a_i}{2}-3t(P). $$
Substituting these into the right local term of the same exact identity reduces it to an integer minimization. For the only five possible values of \(p\), the minima are:
- \(936\) at \(p=81\);
- \(972\) at \(p=82\);
- \(1008\) at \(p=83\);
- \(1044\) at \(p=84\);
- \(1080\) at \(p=85\).
So at every vertex the left local term is at most \(888\), while the right local term is at least \(936\). In particular,
$$ 888<936. $$
But the \(m=3\) identity says the sums of those local terms over all 43 vertices are equal. They cannot be. The \(18\)-regular graph disappears, and complementation removes the \(24\)-regular case.
I like how brutally local the contradiction is. There is no averaging rescue: every single vertex is already at least 48 units on the wrong side.
What is actually left#
A hypothetical \((5,5)\)-good graph on 43 vertices must therefore be prime, connected, co-connected, twin-free, and outside the two regular boundary cases. If it is regular, its degree must be one of
$$ 19,20,21,22,23. $$
Mixed degree distributions also remain possible. The local integer model behind the endpoint proof rejects many numerical states, but its survivors are necessary conditions rather than adjacency matrices. Likewise, being prime does not mean being asymmetric: automorphisms with several moved orbits can survive.
That is the useful shape of the result. It does not settle \(R(5,5)\), but it says an order-43 witness cannot be assembled from homogeneous pieces and cannot balance itself on either edge of the degree interval. Any surviving graph has to be structurally less obliging than that.
Notebook references: C-0228, C-0229