Research · Papers · Exact answers in open problems · MF-187
Minimum degree bounds for (J4, J8; N)-graphs at orders 30 and 31
δ(G) ≥ 4 for every (J4,J8;30)-graph and δ(G) ≥ 5 for every (J4,J8;31)-graph
Published 2026-09-06
For everyone
Plain summary
Ramsey numbers tell us how large a graph must be before specific subgraphs unavoidably appear. A longstanding open question asks for the Ramsey number R(J4, J8), where J_k is a complete graph on k vertices missing one edge. This number is known to lie in the range [30, 32].
This work inspects hypothetical graphs on 30 and 31 vertices that avoid these patterns. By using automated SAT solvers to test every way a low-degree vertex could attach to smaller subgraphs, we prove that vertices cannot have very few connections. Every valid graph on 30 vertices must have at least 4 edges at every vertex, and every valid graph on 31 vertices must have at least 5. The proof is verified by proof checkers, though whether this minimum-degree property appeared in earlier literature remains unverified.
Result
Let J_k = K_k - e. A graph G is a (J4, J8; N)-graph if |V(G)| = N, G contains no induced J4, and every 8-vertex subset spans at least 2 edges (equivalently, the complement of G contains no J8).
For orders N = 30 and N = 31:
- Every (J4, J8; 30)-graph satisfies δ(G) ≥ 4.
- Every (J4, J8; 31)-graph satisfies δ(G) ≥ 5.
Paired with the classical ceiling Δ(G) ≤ 12, these bounds restrict the degree sequences of any graphs realizing R(J4, J8) ∈ [30, 32].
Setting and definitions
Let G = (V, E) be a simple undirected graph on N vertices. For v ∈ V, N(v) is the open neighborhood, N[v] = N(v) ∪ {v} is the closed neighborhood, and deg(v) = |N(v)|. The minimum and maximum degrees of G are δ(G) and Δ(G).
A graph H is (J4, J_k)-good if H is induced-J4-free and every k-set in H spans at least 2 edges. The Ramsey number R(J4, J_k) is the smallest integer N admitting no (J4, J_k; N)-graph. Classical anchor evaluations include:
- R(J3, J8) = 13.
- R(J4, J7) = 28.
- The unique (J4, J7; 27)-graph is the complement of the Schläfli graph (McNamara and Radziszowski, 1991).
For any vertex v in a (J4, J8; N)-graph G:
- The induced subgraph G[N(v)] contains no J3 = K_3 - e (a 2-edge path P3), forcing Δ(G[N(v)]) ≤ 1 (a matching plus isolated vertices).
- G[N(v)] is (J3, J8)-good, giving deg(v) ≤ R(J3, J8) - 1 = 12 and therefore Δ(G) ≤ 12.
- The vertex-deleted neighborhood H = G - N[v] is a (J4, J7; N - 1 - deg(v))-graph. Since R(J4, J7) = 28, |V(H)| ≤ 27, yielding the baseline bound δ(G) ≥ N - 28.
Method
The bounds δ(G) ∉ {N - 28, N - 27} for N ∈ {30, 31} are established by encoding all candidate gluing extensions into SAT and refuting them with certified solvers:
- Case δ(G) = N - 28:
- For N = 30, deg(v) = 2 forces |V(H)| = 27.
- For N = 31, deg(v) = 3 forces |V(H)| = 27.
- In both cases, H = G - N[v] is uniquely the 27-vertex Schläfli complement.
- Because Δ(G[N(v)]) ≤ 1, the edge structure on N(v) is completely fixed by its matching size.
- SAT encodings of the gluing extensions across N[v] produced unsatisfiable formulas, certified UNSAT via drat-trim.
- Case δ(G) = N - 27:
- For N = 30, deg(v) = 3 forces |V(H)| = 26.
- For N = 31, deg(v) = 4 forces |V(H)| = 26.
- The subgraph H is a (J4, J7; 26)-graph with δ(H) ≥ 9.
- All admissible candidates for H and matching configurations on N(v) were generated and encoded as gluing cells.
- Every gluing cell returned UNSAT within 1.6 to 2.4 seconds, verified by DRAT certificates and confirmed by an independent in-process CaDiCaL replay.
Discussion
These minimum degree bounds apply specifically to N ∈ {30, 31}. They do not settle whether (J4, J8; 30)- or (J4, J8; 31)-graphs exist, nor do they fix the value of R(J4, J8), which Wesley (arXiv:2606.17021) bounded in [30, 32].
The gluing procedure follows the framework of Goedgebeur and Van Overberghe (arXiv:2107.04460). An earlier scout entry cited R(K_4-e, K_8), a misprint for R(J4, J8); R(J4, K8) is a separate parameter satisfying 36 ≤ R(J4, K8) ≤ 39.
No earlier published statements of these minimum-degree constraints were identified in the literature, so their historical novelty is unverified.
For everyone — the takeaway
What this means
Computing Ramsey numbers by exhaustive search is impossible because the number of potential graphs grows exponentially. Instead, researchers use structural properties to rule out large classes of candidate graphs.
Showing that any 30-vertex graph must have at least 4 edges per vertex, and any 31-vertex graph at least 5, significantly shrinks the search space for determining R(K_4 - e, K_8 - e).
Attribution and prior art
Prior art: Wesley (arXiv:2606.17021) identifies R(J4,J8) in [30,32] as the next open case, building on the gluing framework from Goedgebeur-Van Overberghe (arXiv:2107.04460). An earlier reference to "R(K_4-e, K_8)" was a misprint for R(J4,J8), which is distinct from R(J4,K8) where 36 <= R <= 39. Sources: Radziszowski, Small Ramsey Numbers (dynamic survey)
Register references
- Register Entry: MF-187
- Proof Receipts:
lanes/ramsey-k4e-k8/BANK-CANDIDATES.md(RAM-05),REPORT.md - Data Artifacts:
frontier/ramsey/glue/C26_n30/,glue/C26_n31/ - Prior Art:
- Wesley, arXiv:2606.17021 (bounds R(J4, J8) in [30, 32])
- Goedgebeur and Van Overberghe, arXiv:2107.04460 (gluing framework)
- McNamara and Radziszowski (1991) (uniqueness of the (J4, J7; 27)-graph / Schläfli complement)
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 2 of 2 receipt files bundled (20 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.