Erdoes #545 - working report - Erdős Problem a Day

Erdős problem #545 — exact eight-edge colex value and a missed uniform theorem

Date: 2026-07-26 UTC

Claim labels

(a) elementary-rigorous: a complete proof is given here, using only explicitly proved lemmas.
(b) rigorous-modulo-named-theorem: the deduction is rigorous from a precisely named and checked published theorem.
(c) plausible/structural-unverified: an interpretation, heuristic, or unverified comment claim.
(d) computational-only: established by the supplied finite checker, not promoted to a general theorem on that basis alone.

Step 0: source and collision audit

Live-origin caveat

(d) I used the required Bright Data browser path three times (both hostnames and, on the final attempt, a different proxy location). At 23:04, 23:05, and 23:19 UTC the browser reached Cloudflare, but the erdosproblems.com origin returned HTTP 522 “Connection timed out.” This was an origin failure, not a direct-datacenter Cloudflare challenge.

(d) The freshest complete retrievable representations were the Internet Archive captures of the problem page at 2026-07-09 21:32:18 UTC and the full 16-comment thread at 2026-07-09 21:44:04 UTC. I cross-checked these against a search-engine rendering crawled in the last month and against official database commit e5145a87748092babd7b4f990c493c0ab46edf10, dated 2026-07-26. The live origin itself was therefore not readable on the run date; all status claims below are the freshest independently agreeing snapshots, not a pretence of a successful live fetch.

Verbatim statement

> Let $G$ be a graph with $m$ edges and no isolated vertices. Is the Ramsey number $R(G)$ maximised when $G$ is 'as complete as possible'? That is, if $m=\binom{n}{2}+t$ edges with $0\leq t<n$ then is\[R(G)\leq R(H),\]where $H$ is the graph formed by connecting a new vertex to $t$ of the vertices of $K_n$?

Status and participation markers

(d) Every retrievable representation agreed on:

status: OPEN, with tooltip “This is open, and cannot be resolved with a finite computation”;
comment-status widget: “There are no solutions, partial or complete, claimed in the comments”;
“Interested in collaborating”: None;
“Currently working on this problem”: None;
“I am working on formalising the results”: None;
one “Likes this problem” marker, from Dogmachine;
page last edited 02 December 2025;
16 comments.

Thus no displayed claimed proof, solution, falsification status, current worker, or interested collaborator triggered the mandatory stop rule.

Listed remarks and all 16 comments

(d) The page remarks say that this is a question of Erdős and Graham; that the weaker bound

\[ R(G)\leq 2^{O(\sqrt m)} \]

was proved by Sudakov; that the displayed comparison fails for $2\leq m\leq5$ and $7\leq m\leq9$; and that this is problem #10 in the Ramsey Theory section of Chung's graph-problem collection.

(d) The following is a complete content inventory of the 16 posts, organized by discussion branch with post IDs shown. These are reports of what commenters wrote, not endorsements of unchecked assertions.

1. LouisD (post 1541) asked where the problem occurs in Erdős's 1984 paper.

2. Woett (1542) pointed to the Erdős–Graham paper and distinguished another decomposition question.

3. Thomas Bloom (1543) located the sentence on p.11 of the 1984 paper, the explicit question on p.526 of Erdős–Graham, and explained that the more detailed formulation came from Chung's collection.

4. LouisD (1546) said the source issue was resolved.

5. LouisD (1545) observed $R(3K_2)=8>R(K_3)=6$, gave \(R(6K_2)=17

6. Thomas Bloom (1547) reported finding no further literature and noted Sudakov's statement that no progress was then known.

7. LouisD (1549) used $R(K_5-e)=22$ to obtain failures for eight and nine edges, and explicitly said the exact value of $R(\widehat K_{4,2})$ remained interesting.

8. Adenwalla (1550) flagged a matching-number typo in post 1545.

9. LouisD (1552) corrected it to $R(6K_2)=17$.

10. LouisD (1551) summarized failures at $m\in\{3,4,5,7,8,9\}$, attributed them to matchings, and said $m=6$ should hold.

11. LouisD (1553) observed that an eventual (“sufficiently large $m$”) version should not be marked finitely falsifiable.

12. Adenwalla (1557) added the failure at $m=2$.

13. StijnC (1562) discussed complete bipartite graphs versus cliques asymptotically and repeated the $m=2$ failure.

14. Adenwalla (1564) suggested first treating the triangular case $t=0$.

15. StijnC (1567) discussed candidate structured counterexamples, wheels, multipartite graphs, and the expected difficulty of a direct comparison.

16. Thomas Bloom (1568) linked Burr's table of all isolate-free graphs with at most six edges and concluded that $m=6$ holds.

(b) There is a bibliographic slip in post 1568: its linked DOI, 10.1002/jgt.3190070108, is Stefan Burr, Diagonal Ramsey numbers for small graphs, Journal of Graph Theory 7 (1983), 57–69, not a 1989 paper. Its abstract does say that all 113 isolate-free graphs with at most six edges are determined.

Literal statement versus operative open residue

(a) The verbatim universal statement is literally false, because the page itself lists finite counterexamples.

(c) Since the authoritative page nevertheless retains OPEN status and its comments explicitly discuss modifying the question to “$m$ sufficiently large,” the only coherent open residue is the eventual version. The words “sufficiently large” are not present in the displayed statement, so this is an interpretation forced by the page's own status/remarks, not a silently altered theorem statement. Nothing below claims to settle that eventual question.

Literature audit

Primary sources actually checked

1. (b) Erdős and Graham, On partition theorems for finite graphs (1975), pp.515–527, ask on p.526 whether the complete graph maximizes the (multi-colour) Ramsey number among graphs with the same triangular number of edges.

2. (b) Erdős, On some problems in graph theory, combinatorial analysis and combinatorial number theory (1984), p.11, states that the Ramsey number should be maximal for a graph “as complete as possible.”

3. (b) Sudakov, A conjecture of Erdős on graph Ramsey numbers, Advances in Mathematics 227 (2011), 601–609, DOI 10.1016/j.aim.2011.02.004, proves the weaker uniform estimate $R(G)\leq2^{c\sqrt m}$.

4. (b) Bradač–Morawski–Sudakov–Wigderson, Ordered Ramsey numbers of graphs with $m$ edges, Proceedings of the AMS 154 (2026), 927–942, DOI 10.1090/proc/17442, says in its introduction that the unordered Erdős–Graham conjecture remains open and is likely very difficult. This is the newest primary-source status statement I found.

5. (b) Burr–Erdős–Faudree–Schelp, On the Difference between Consecutive Ramsey Numbers, Utilitas Mathematica 35 (1989), 115–118, proves a directly relevant clique-extension theorem on pp.117–118.

6. (b) Calvert–Schuster–Radziszowski, Computing the Ramsey Number $R(K_5-P_3,K_5)$, identifies $K_5-P_3$ equivalently as $K_4$ plus a vertex joined to two core vertices, and restates the 1989 extension theorem.

7. (b) Cockayne–Lorimer, The Ramsey number for stripes, J. Austral. Math. Soc. 19 (1975), 252–256, gives the general multicolour matching formula; the two-colour diagonal specialization is $R(kK_2)=3k-1$.

(c) Exact-title, exact-phrase, citation-chain, and graph-name searches (K_5-P_3, K_5 minus two incident edges, “as complete as possible,” and graphs with $m$ edges) found no primary source claiming the full extremal comparison. Failure to find a paper is not proof none exists; the 2026 primary source is the positive evidence for current openness.

Missed uniform partial result

Write $\widehat K_{n,t}$ for $K_n$ plus a new vertex joined to exactly $t$ vertices of the clique.

(b) Theorem 4 of Burr–Erdős–Faudree–Schelp says that, for $a,b\geq3$ and $a+b\geq8$,

\[ R\!\left(\widehat K_{a,p},\widehat K_{b,q}\right)=R(K_a,K_b), \qquad p=\left\lceil\frac{a}{b-1}\right\rceil,\quad q=\left\lceil\frac{b}{a-1}\right\rceil . \]

(b) On the diagonal $a=b=n\geq4$, both ceilings equal $2$, hence

\[ R(\widehat K_{n,2})=R(K_n). \]

By subgraph monotonicity,

\[ R(K_n)=R(\widehat K_{n,1})=R(\widehat K_{n,2}) \qquad(n\geq4). \]

(b) This already gives

\[ R(\widehat K_{4,2})=R(K_4)=18. \]

Thus the exact value asked for in post 1549 was in the literature, although not cited on the problem page.

(a) This theorem does not prove the Erdős #545 comparison. It evaluates the proposed maximizer for $t\leq2$; it does not show that every graph with the same number of edges has Ramsey number at most that value.

Independent elementary proof of the exact $m=8$ value

Set

\[ H=\widehat K_{4,2}=K_5-P_3. \]

It has eight edges: the six edges of $K_4$, plus two incident to the fifth vertex.

Lemma 1: $R(K_3,K_4)\leq9$

(a) Consider a red/blue colouring of $K_9$. If there is a red triangle, stop. Otherwise the red graph is triangle-free.

If some vertex has at least four red neighbours, those neighbours have all mutual edges blue, giving a blue $K_4$.
Otherwise every red degree is at most three. Nine vertices cannot all have red degree three, since the degree sum would be the odd number $27$. Hence some vertex $v$ has red degree at most two and therefore has at least six blue neighbours.
Every two-colouring of $K_6$ has a monochromatic triangle: at a vertex, three incident edges have one colour; either one edge among their other endpoints has that colour or all three have the other colour. Applied to the six blue neighbours of $v$, a red triangle is excluded, so they contain a blue triangle. Together with $v$, this is a blue $K_4$.

Lemma 2: $R(K_3,K_5)\leq14$

(a) Suppose a colouring of $K_{14}$ has neither a blue triangle nor a red $K_5$, and choose $v$.

If $v$ has at least nine red neighbours, Lemma 1 with colours exchanged inside any nine of them gives either a blue triangle or a red $K_4$; the former is forbidden and the latter extends with $v$ to a red $K_5$.
Otherwise $v$ has at least five blue neighbours. No two of those five can have a blue edge, so they form a red $K_5$.

Both alternatives contradict the assumption.

Upper bound $R(H)\leq18$

(a) Every colouring of $K_{18}$ has a monochromatic $K_4$. Indeed, a vertex has at least nine incident edges of one colour; Lemma 1 in that nine-vertex neighbourhood yields either a same-colour triangle, which extends through the vertex, or an opposite-colour $K_4$.

Take a red $K_4$ on a vertex set $S$, and let $T$ be the remaining 14 vertices. Assume for contradiction that there is no monochromatic $H$.

(a) Every $x\in T$ has at most one red neighbour in $S$, since two red neighbours would extend the red core $S$ to a red copy of $\widehat K_{4,2}$.

(a) The blue graph on $T$ contains no triangle. If $x,y,z\in T$ formed a blue triangle, their red incidences into $S$ would total at most three. Some $s\in S$ would therefore be blue-adjacent to all of $x,y,z$, so $\{s,x,y,z\}$ would be a blue $K_4$. Among the other three vertices of $S$, one has at most one red edge to $\{x,y,z\}$, again because there are at most three such red incidences in total. That vertex has at least two blue neighbours in the blue $K_4$, producing a blue $H$, contradiction.

(a) Lemma 2 applied to $T$ now gives a red $K_5$, which contains a red $H$. This final contradiction proves $R(H)\leq18$.

Lower bound $R(H)\geq18$

(a) Colour $K_{17}$ on $\mathbb Z/17\mathbb Z$ red when the nonzero difference of the endpoints is a quadratic residue

\[ Q=\{1,2,4,8,9,13,15,16\}, \]

and blue otherwise. Since $-1\in Q$, this is an undirected colouring.

(a) There is no red $K_4$. After translating one vertex of a hypothetical red $K_4$ to $0$, the other three vertices would form a triangle in the difference graph on $Q$. Its adjacency lists are

\[ \begin{array}{c|c@{\qquad}c|c} 1&2,9,16&2&1,4,15\\ 4&2,8,13&8&4,9,16\\ 9&1,8,13&13&4,9,15\\ 15&2,13,16&16&1,8,15, \end{array} \]

and direct inspection shows no triangle. Multiplication by the nonsquare $3$ interchanges residues and nonresidues, so the blue graph is isomorphic to the red graph and also has no $K_4$.

(a) Since $H$ contains $K_4$, this colouring has no monochromatic $H$. Hence $R(H)\geq18$, and together with the upper bound,

\[ \boxed{R(K_5-P_3)=R(\widehat K_{4,2})=18}. \]

Exact comparison with the eight-edge matching

Matching formula, proved here

(a) For every $k\geq1$,

\[ R(kK_2)=3k-1. \]

For the lower bound, colour $K_{3k-2}$ using a partition $A\cup B$, where $|A|=k-1$ and $|B|=2k-1$. Colour every edge meeting $A$ red and every edge inside $B$ blue. A red matching uses a distinct vertex of $A$ for every edge, and a blue matching is contained in the odd set $B$, so neither has $k$ edges.

For the upper bound, induct on $k$. In a two-colouring of $K_{3k-1}$, if a red edge and a blue edge share a vertex, delete their three vertices. The remaining $K_{3(k-1)-1}$ has a monochromatic $(k-1)$-matching by induction, and the deleted edge of the matching's colour extends it. If no differently coloured incident edges exist, connectedness of the complete graph forces all edges to have one colour, which plainly contains a $k$-matching.

(a) At $k=8$,

\[ R(8K_2)=23. \]

Both $8K_2$ and $H=\widehat K_{4,2}$ have eight edges and no isolated vertices, but

\[ \boxed{R(8K_2)-R(H)=23-18=5}. \]

(a) The page already knew that $m=8$ is a counterexample, via the weaker estimate $R(H)\leq22$. The verified advance here is the exact colex value $18$ and exact gap $5$, plus identification of the missed uniform 1989 theorem. This is not claimed as new to the literature.

Re-verification code and results

The complete standalone standard-library checker is erdos545_wave5y_verify.py, 291 lines, SHA-256

b592849d64796db0ffe949990aba7c5a452c2efac4dec9eb23f1a4572174a43a

Run from the repository root:

python runs/erdos545_wave5y_verify.py

It performs the following independent checks:

1. (d) constructs $\widehat K_{4,2}$, checks eight edges/no isolates, and verifies that its complement in $K_5$ consists of two incident edges;

2. (d) constructs the Paley $K_{17}$ colouring, checks all $\binom{17}{4}=2380$ four-sets and all embeddings of $H$, finding no monochromatic $K_4$ or $H$;

3. (d) uses an implemented-from-scratch DPLL solver, not PySAT, to exhaust the nine canonical red-degree branches for a $(K_3,K_4;9)$-good colouring; all are UNSAT after 2931 search nodes;

4. (d) checks the degree split proving $R(3,5)\leq14$ and all $5^3=125$ possible red-incidence patterns of a hypothetical blue triangle into the red $K_4$;

5. (d) checks the $K_{22}$ matching construction and every induction-size identity through $k=8$;

6. (d) checks the diagonal parameter substitution $p=q=2$ in the cited BEFS theorem.

Observed output:

[OK] H=K-hat_{4,2}=K_5-P_3 has 5 vertices, 8 edges, and no isolates.
[OK] Paley(17) colors 68 edges red and 68 blue; exhaustive checks find 0 monochromatic K_4 and 0 monochromatic H.
[OK] From-scratch DPLL proves R(3,4)<=9: all 9 canonical degree branches are UNSAT (2931 search nodes).
[OK] Upper-bound certificate checked: R(3,5)<=14 reduction and all 125 external-incidence patterns.
[OK] Together with the report's deductions, these certify R(K_5-P_3)<=18.
[OK] The K_22 matching coloring avoids monochromatic 8K_2, and the induction arithmetic certifies R(8K_2)=23.
[OK] BEFS Theorem 4's diagonal parameters specialize to p=q=2 (the cited theorem itself is a literature dependency).
VERIFIED: R(K_5-P_3)=18 and R(8K_2)=23, hence the exact gap is 5.

Runtime on this VM was about 1.4 seconds with peak RSS about 11 MB.

What remains, exactly

(a) Even the triangular subcase

\[ \forall G\quad \left(e(G)=\binom n2,\ \delta(G)\geq1\right) \Longrightarrow R(G)\leq R(K_n) \]

is still the original Erdős–Graham conjecture. Therefore any eventual solution of #545 must at minimum supply this uniform comparison for all sufficiently large $n$.

(a) The 1989 theorem only identifies the Ramsey number of the proposed colex target for $t\leq2$; it supplies no domination statement for arbitrary $G$.

(b) Sudakov's $2^{O(\sqrt m)}$ theorem controls the correct exponential scale but not the constants sharply enough to compare every $G$ with the specific colex graph. The 2026 ordered-Ramsey paper still records lack of progress on the unordered extremal comparison.

(a) Finite enumeration cannot settle the eventual quantifier. A genuinely closing lemma would have to convert only the edge count of an arbitrary graph into the sharp Ramsey comparison with $K_n$ (already for $t=0$), or else produce an infinite counterexample family. Neither is supplied here.

PARTIAL: proved from scratch that the eight-edge colex graph has Ramsey number 18 (so its exact matching counterexample gap is 5), and located the missed 1989 theorem $R(\widehat K_{n,2})=R(K_n)$ for every $n\geq4$; the eventual extremal comparison remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger