# P2508: A 43-vertex graph for the diagonal Ramsey problem R(5,5)

- ID: `P2508`
- Reference: `ramsey-55-43-graph`
- Page: https://theoremdb.org/statements/P2508
- Record maturity: Reviewed problem with recorded work

## Problem

Does there exist a simple graph \(G\) on \(43\) vertices such that neither \(G\) nor its complement contains a copy of \(K_5\)?

### Remarks

- **Remark.** Equivalently, the graph must have clique number and independence number at most four.
- **Remark.** Such a graph would be a two-coloring of the edges of \(K_{43}\) with no monochromatic \(K_5\).

### What counts as a solution

- Supply a 43-vertex adjacency matrix and an exact certificate or independently checkable enumeration showing that all 962598 five-vertex subsets induce between one and nine edges.

## Status

The checked 42-vertex graph certifies \(R(5,5)\ge43\); the order-43 witness remains missing, so existence of a 43-vertex graph with clique and independence number at most four remains open. [2](#reference-2)

## Work

### Evidence for the current status

**Computation 1 (The cited public graph certifies R(5,5) at least 43).** The checked 42-vertex graph certifies \(R(5,5)\ge43\); the order-43 witness remains missing, so existence of a 43-vertex graph with clique and independence number at most four remains open.

The first record of `r55_42some.g6` decodes to a graph \(G\) on 42 vertices with 425 edges. Exhaustive enumeration of its
\[
\binom{42}{5}=850{,}668
\]
five-vertex subsets gives the induced-edge histogram
\[
[0,6078,31577,99576,192531,225712,173847,87463,27923,5961,0].
\]
The entries at positions 0 and 10 vanish. Thus every five-set has at least one edge and at least one nonedge. The graph contains no \(K_5\), and its complement contains no \(K_5\).

By definition, \(R(5,5)\) is the least order at which every graph contains a \(K_5\) or an independent five-set. This 42-vertex witness proves
\[
R(5,5)>42,\qquad R(5,5)\geq43.
\]
A 43-vertex witness would instead prove \(R(5,5)\geq44\). The candidate asks for that larger witness. Its cited graph and digest have order 42.

### Background and intake notes

The diagonal Ramsey number \(R(5,5)\) has resisted an exact determination for decades. A single valid graph changes its best lower bound.

- Original intake status: The published bounds as of 2026-07-24 are \(43\le R(5,5)\le46\). A 43-vertex witness would raise the lower bound to \(44\).
- Known 42-vertex Ramsey graphs provide concrete starting points for vertex extension, edge switching, and SAT neighborhoods. Record the seed graph and every fixed-edge region searched.
- A failed search under regularity, circulant symmetry, or a prescribed degree sequence rules out only that named family. Each restriction belongs in the saved attempt record.

### Prior approaches

- **Route 1** (inconclusive): The candidate cites a 42-vertex collection, while current sources retain 43 as the best lower bound. [1](#reference-1) [4](#reference-4) [3](#reference-3) [5](#reference-5)

### Runnable artifacts

- **Artifact 1** (reproduced): The decoder reproduces both graph digests and checks every five-set in the graph and complement. [2](#reference-2)

### Computational notes

- The first graph in the public r55_42some.g6 collection was decoded independently. Its first-line SHA-256 is ab0b10364ac62ab07f662c0ed4e8b47a44956f63a78356b64ae64ccb6520ecb0. It has 42 vertices and 425 edges, with degrees 19 through 22. Exact enumeration of all 850668 five-vertex subsets found no \(K_5\) in the graph or its complement.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `ramsey-55-43-graph`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Vigleik Angeltveit and Brendan D. McKay, R(5,5) ≤ 46, Journal of Graph Theory 112(3) (2026), 198-208. Main theorem and current interval for R(5,5) https://doi.org/10.1002/jgt.70029
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - Proves the current upper bound R(5,5) at most 46.
2. <a id="reference-2"></a>Brendan D. McKay, r55_42some.g6, Ramsey graph data, Australian National University. Brendan McKay, Combinatorial Data, r55_42some.g6, first line; independently decoded and checked on 2026-07-24 https://users.cecs.anu.edu.au/~bdm/data/r55_42some.g6
   - Also cited at First line of Brendan McKay's r55_42some.g6 collection, retrieved and verified on 2026-07-24
   - dataset; dataset source; r55_42some.g6 independently decoded and checked 2026-07-24; checked 2026-08-01
   - Source use: original_summary
   - Supplies the exact 42-vertex graph whose clique and independence numbers certify R(5,5) at least 43.
3. <a id="reference-3"></a>Brendan D. McKay, Ramsey graph data, Australian National University, author-maintained data page. R(5,5) data index and linked 42-vertex witness collection https://users.cecs.anu.edu.au/~bdm/data/ramsey.html
   - website; reference source; web version checked 2026-08-01; checked 2026-07-24
   - Source use: citation_only
   - Indexes the public 42-vertex R(5,5) witness collection used for the packet certificate.
   - Source named by the research packet.
4. <a id="reference-4"></a>Brendan D. McKay and Stanisław P. Radziszowski, Subgraph Counting Identities and Ramsey Numbers, Journal of Combinatorial Theory, Series B 69 (1997), 193-209. Subgraph-counting bounds for R(5,5) https://users.cecs.anu.edu.au/~bdm/papers/r55.pdf
   - journal_article; primary source; author-hosted version of record checked 2026-07-26; checked 2026-08-01
   - Source use: citation_only
   - Develops the subgraph-counting identities behind earlier bounds for R(5,5).
5. <a id="reference-5"></a>Stanisław P. Radziszowski, Small Ramsey Numbers, Dynamic Survey DS1, Electronic Journal of Combinatorics (2026 revision). R(5,5) entry in the 2026 survey revision https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1
   - journal_article; secondary source; DS1 revision dated 2026-04-24; checked 2026-08-01
   - Source use: citation_only
   - Records the current published interval 43 through 46 for R(5,5).