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

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

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

1Remarks

Remark 1. Equivalently, the graph must have clique number and independence number at most four.

Remark 2. Such a graph would be a two-coloring of the edges of \(K_{43}\) with no monochromatic \(K_5\).

2What 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.

1Status

Saved packet · July 24, 2026

What counts as a solution

Saved packet status (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.^[2]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 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] Relevance to this problem For A 43-vertex graph for the diagonal Ramsey problem R(5,5), record r55-claim-public-graph-lower-bound-43 (“The cited public graph certifies R(5,5) at least 43”) records a bound, answer, status fact, or structural consequence. The record states: 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. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Scope the first graph6 record in McKay's public r55_42some.g6 collection Sources Reference 2 Details 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. Open full record →
The candidate cites a 42-vertex collection, while current sources retain 43 as the best lower bound.	Trace	Outcome: Inconclusive Evidence: Inconclusive The recorded search or audit ended without settling the question.
attempt · Route 1 The candidate cites a 42-vertex collection, while current sources retain 43 as the best lower bound.^[1][4][3][5] Relevance to this problem For A 43-vertex graph for the diagonal Ramsey problem R(5,5), record r55-attempt-order-43-witness-audit (“The order-43 witness remains missing”) documents a concrete method, search boundary, or failed route. The record states: The candidate cites a 42-vertex collection, while current sources retain 43 as the best lower bound. Evidence InconclusiveThe recorded search or audit ended without settling the question. Scope the candidate record and current primary sources checked for an explicit Ramsey(5,5,43) graph through 2026-07-24 Sources Reference 1, Reference 4, Reference 3, Reference 5 What happened The candidate contains no graph6 record or adjacency matrix of order 43. Its computation identifies the first record in `r55_42some.g6`. The leading graph6 byte confirms order 42. McKay and Radziszowski reported 656 known \((5,5,42)\)-graphs in section 4 of their 1997 paper. They checked that those graphs could not be extended by one vertex and conjectured both \(R(5,5)=43\) and completeness of the 656-graph collection. The completeness statement remains a conjecture in that paper, so the failed extensions do not exclude every possible 43-vertex graph. Angeltveit and McKay's 2026 paper states that Exoo's lower bound 43 remains the best and proves the current upper bound 46. McKay's data page likewise says that graphs with 43 through 47 vertices could exist. The current interval is \[ 43\leq R(5,5)\leq46. \] An explicit \((5,5,43)\)-graph would improve its lower endpoint to 44. No such artifact was supplied or located in the checked primary sources. Related: Computation 1 Open full record →
The decoder reproduces both graph digests and checks every five-set in the graph and complement.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 The decoder reproduces both graph digests and checks every five-set in the graph and complement.^[2] Relevance to this problem For A 43-vertex graph for the diagonal Ramsey problem R(5,5), record r55-artifact-first-public-42-graph-check (“Exhaustive certificate for the first public 42-vertex graph”) supplies evidence or a replay used to check the packet. The record states: The decoder reproduces both graph digests and checks every five-set in the graph and complement. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope all five-element subsets of the first 42-vertex graph in r55_42some.g6 Sources Reference 2 Entry point `join source_lines with newline and run with python3` Runtime CPython 3.9 or later, standard library only Details The graph6 short header is the byte `i`. Since \(\operatorname{ord}(i)-63=42\), the record has 42 vertices. Its 144 payload characters supply 864 bits. The first \(\binom{42}{2}=861\) bits encode the unordered pairs in graph6 order, and the final three bits are zero padding. The graph6-line SHA-256 includes the terminating line feed. For a second digest, the decoder visits edges in graph6 order and serializes each edge \((u,v)\) as the two bytes `u,v`. The 425 edges therefore give 850 digest bytes. The executable counts the number of induced edges on each five-set. Ten edges would be a \(K_5\) in the graph, while zero edges would be a \(K_5\) in the complement. Both counts are zero. The complete histogram also fixes every intermediate count and makes the check reproducible without a graph library. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion material

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.

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.

How the 3 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemA 43-vertex graph for the diagonal Ramsey problem R(5,5)

All 2 recorded relations between these records and the problem

2See also

Erdős-Hajnal conjectureramsey theory
An explicit exponential lower bound for diagonal Ramsey numbersramsey theory
Existence and value of the diagonal Ramsey exponential limitramsey theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“A 43-vertex graph for the diagonal Ramsey problem R(5,5).” TheoremDB. P2508. Problem statement; statement text SHA-256 5cacb3cdca6a3c16aed24d9f40a410ed52b7fcc60b0a9982fb4058336bd50785. https://theoremdb.org/statement/?ref=P2508

BibTeX

@misc{theoremdb-problem-5cacb3cdca6a3c16aed24d9f40a410ed52b7fcc60b0a9982fb4058336bd50785,
  title = {{A 43-vertex graph for the diagonal Ramsey problem R(5,5)}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 5cacb3cdca6a3c16aed24d9f40a410ed52b7fcc60b0a9982fb4058336bd50785},
  url = {https://theoremdb.org/statement/?ref=P2508}
}

Plain text: Built Markdown snapshot

This problem includes 3 records joined by 2 typed links, sourced from users.cecs.anu.edu.au^[3], current as of July 24, 2026.

1Lean verification

1References

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). ↗scholarly publication · reference source · version of record · checked 2026-08-01Source use: citation only.Proves the current upper bound R(5,5) at most 46.Also cited at Vigleik Angeltveit and Brendan D. McKay, R(5,5) at most 46, Journal of Graph Theory 112 (2026), Introduction and Theorem 1.1; Brendan McKay and Stanislaw Radziszowski, Subgraph Counting Identities and Ramsey Numbers, Journal of Combinatorial Theory B 69 (1997), section 4, pages 9-10; McKay's Combinatorial Data page, section The largest known Ramsey(5,5)-graphs; checked 2026-07-24.For A 43-vertex graph for the diagonal Ramsey problem R(5,5): The candidate cites a 42-vertex collection, while current sources retain 43 as the best lower bound.
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. ↗dataset · dataset source · r55_42some.g6 independently decoded and checked 2026-07-24 · checked 2026-08-01Source use: original summary.Supplies the exact 42-vertex graph whose clique and independence numbers certify R(5,5) at least 43.Also cited at First line of Brendan McKay's r55_42some.g6 collection, retrieved and verified on 2026-07-24.For A 43-vertex graph for the diagonal Ramsey problem R(5,5): The decoder reproduces both graph digests and checks every five-set in the graph and complement.
Packet source. Brendan D. McKay, Ramsey graph data, Australian National University, author-maintained data page. R(5,5) data index and linked 42-vertex witness collection. ↗website · reference source · web version checked 2026-08-01 · checked 2026-07-24Source use: citation only.Indexes the public 42-vertex R(5,5) witness collection used for the packet certificate.Also cited at McKay's public Ramsey graph data, current Ramsey literature, and an independent exhaustive check performed on 2026-07-24.Source named by the research packet.For A 43-vertex graph for the diagonal Ramsey problem R(5,5): McKay's public Ramsey graph data, current Ramsey literature, and an independent exhaustive check performed on 2026-07-24
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). ↗journal article · primary source · author-hosted version of record checked 2026-07-26 · checked 2026-08-01Source use: citation only.Develops the subgraph-counting identities behind earlier bounds for R(5,5).
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. ↗journal article · secondary source · DS1 revision dated 2026-04-24 · checked 2026-08-01Source use: citation only.Records the current published interval 43 through 46 for R(5,5).

Explicit graph-construction target for improving the lower bound on the diagonal Ramsey number.

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

1Remarks

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Remarks

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance