reconstructed from a secondary citation.

Pre-2026 general bound

Gyárfás and Tuza,

An Upper Bound on the Ramsey Number of Trees,

Discrete Mathematics 66 (1987), 309–310, prove for a \(d\)-edge tree

For the live page's \(n\)-vertex convention this is

This improved the original coefficient but did not approach \(q\) for

fixed \(q\).

Exact two-colour case for large trees

Yi Zhao,

Proof of the \((n/2-n/2-n/2)\) Conjecture for Large \(n\),

Electronic Journal of Combinatorics 18 (2011), P27, states as Corollary

2.2 that every sufficiently large \(n\)-vertex tree satisfies

Thus the live problem is already known for \(q=2\).

Exact bounded-degree Erdős–Sós theorem

Pokrovskiy,

Hyperstability in the Erdős–Sós Conjecture,

arXiv:2409.15191v1, states:

> Theorem 1.16. Let \(\Delta^{-1}\gg d^{-1}\). Let \(G\) be an

> \(N\)-vertex graph with \(e(G)>(d-1)N/2\). Then \(G\) contains a copy

> of every \(d\)-edge tree \(T\) having \(\Delta(T)\leq\Delta\).

The companion preprint

Notes on embedding trees in graphs with \(O(|T|)\)-sized covers

contains the stability and extremal ingredients cited in that proof.

Section 6 of the first paper explicitly restates the Erdős–Graham Ramsey

question as Problem 6.14 and says: “Using Theorem 1.16 we get a proof of

this being true for bounded degree trees.” Both arXiv records exist, each is

still v1, and the quoted theorem and application occur in the PDFs.

March 2026 all-tree asymptotic

Davoodi, Piguet, Řada, and Sanhueza-Matamala,

The asymptotic version of the Erdős–Sós conjecture and beyond,

arXiv:2603.17755v1 (submitted 2026-03-18), is a 104-page preprint.

Its Corollary 1.6 is:

for fixed \(q,\varepsilon>0\), once the sum of the tree orders is

sufficiently large. I also checked its short proof in §3.3; this is not an

inference from the abstract.

Taking \(T_1=\cdots=T_q=T\) gives, uniformly over all \(n\)-vertex trees,

Equivalently, \(R_q(T)\leq qn+o(n)\).

Small values and search misses

The current

Small Ramsey Numbers survey, revision 18, 2026-04-24

records \(R_3(P_3)=5\), \(R_3(P_4)=6\), and \(R_3(P_5)=9\), and says Yang

and Rowlinson determined \(R_3(G)\) for every graph \(G\) with at most four

edges and no isolated vertices. The primary paper is

The Third Ramsey Numbers for Graphs with at Most Four Edges90182-1),

Discrete Mathematics 125 (1994), 399–406.

I searched the current survey, the cited primary papers, arXiv, journal

records, and queries for the exact Erdős–Graham formulation. I found no

post-2025 full proof or falsification. The March 2026 asymptotic paper and the

bounded-degree preprints above were the only directly stronger current

developments found. A search miss is not a proof of nonexistence, so the

claim here is only that no further usable source was located.

Result 1: the bounded-degree regime

Proposition. Fix \(q\geq2\) and \(\Delta\). For all sufficiently large

\(n\), if \(T\) is an \(n\)-vertex tree with

\(\Delta(T)\leq\Delta\), then

Proof. Put

In any \(q\)-edge-colouring of \(K_N\), some colour graph \(G\) has

Since \(N-1=q(n-2)+1\),

The tree \(T\) has \(d=n-1\) edges, so

\((d-1)N/2=(n-2)N/2\). Pokrovskiy's Theorem 1.16 therefore embeds \(T\)

in \(G\), monochromatically. \(\square\)

Relative to the live target this is

so it supplies an explicit additive constant. The only non-elementary input

is the named preprint theorem. Classification: (b).

Result 2: the exact extremal reduction and the missing lemma

For a graph \(T\), let \(\operatorname{ex}(N,T)\) be the maximum number of

edges in an \(N\)-vertex \(T\)-free graph. Pure averaging gives the exact

sufficient condition

Indeed, the largest colour class has at least \(\binom N2/q\) edges. This is

the entire reason problem #548 implies #557.

If the full Erdős–Sós bound

held for every \(n\)-vertex tree, substituting

\(N=q(n-2)+2\) into (1) would prove

The bounded-degree result above is exactly this argument in the regime where

(2) is available.

There is a useful weaker target. At the desired order \(N=qn+C\), the densest

colour has average degree at least

Consequently the live problem would follow from the following restricted

additive embedding lemma:

> For every fixed \(q\), there is a constant \(A_q\) such that every graph

> on \(qn+O_q(1)\) vertices with average degree greater than \(n+A_q\)

> contains every \(n\)-vertex tree.

This is weaker than the full Erdős–Sós conjecture, whose threshold is

\(n-2\), and it is required only for host/tree order ratio near \(q\).

Nevertheless, it is not supplied by current all-tree results.

Corollary 1.4 of arXiv:2603.17755 requires average degree more than

\((1+\varepsilon)(n-1)\), for every fixed \(\varepsilon>0\). Its error is

\(\Theta(\varepsilon n)\). The implication

does not permit setting \(\varepsilon=1/n\). Regularity-based \(n_0\)'s are

in any event enormous and non-uniform as \(\varepsilon\to0\). Thus the exact

missing step is an additive-error, all-tree embedding theorem at fixed host

density. **The reduction is (a) elementary-rigorous; the assessment that no

such theorem was found is an honest literature-search wall.**

No feasible finite computation closes this gap: the asymptotic theorem does

not provide a manageable explicit cutoff below which cases could be checked.

A direct CNF with one forbidden clause per labelled copy has

\(\Theta(qN^2)\) variables/colour constraints but up to

tree-copy clauses. At \(N\sim qn\) this is superexponential in \(n\).

Lazy generation helps tiny instances but does not replace the uniform

embedding lemma.

Result 3: exact stars, from scratch

The page gives only the scale \(qn-O(q)\). The exact result is

This is the diagonal specialization of Burr–Roberts (1973), but the following

proof is self-contained.

Put \(d=n-2\). A colouring avoids \(S_n\) exactly when every vertex has

degree at most \(d\) in every colour. Hence any avoiding colouring of

\(K_M\) must satisfy

At the equality order \(M=qd+1\), every vertex would have degree exactly

\(d\) in every colour. Thus every colour graph would be \(d\)-regular.

• If \(q\) is even and \(n\) is odd, then both \(M=qd+1\) and

\(d=n-2\) are odd. A \(d\)-regular graph on odd order is impossible by

the handshaking lemma. On the other hand, \(K_{qd}\) has a

1-factorisation; grouping its \(qd-1\) perfect matchings into \(q\)

groups of sizes at most \(d\) gives an avoiding colouring. Therefore

\(R_q(S_n)=qd+1\).

• Otherwise, if \(d\) is even, \(M\) is odd and a 2-factorisation of

\(K_M\), grouped \(d/2\) factors per colour, gives an avoiding colouring.

If \(d\) is odd, the nonexceptional case forces \(q\) odd, so \(M\) is

even; a 1-factorisation grouped \(d\) factors per colour does the same.

Thus \(K_{qd+1}\) is avoidable, while (6) rules out \(K_{qd+2}\), giving

\(R_q(S_n)=qd+2\).

This also shows directly why the conjectured leading coefficient \(q\)

cannot be lowered for all trees. **Classification: (a)

elementary-rigorous.** The verifier checks the parity arithmetic for

\(2\leq q,n\leq100\) as a guard against indexing mistakes; the proof, not

that finite check, establishes (5).

Result 4: certified \(q=3,\ n\leq5\) table

Complete census

There are \(1,1,2,3\) unlabelled trees on \(2,3,4,5\) vertices. The verifier

does not assume these counts: it exhausts every \((n-1)\)-edge subgraph of

\(K_n\), keeps the connected ones, canonically relabels them by trying all

\(n!\) permutations, and confirms that the hard-coded cases are exactly the

resulting isomorphism types.

The exact results and upper certificates are:

| Tree \(T\) | \(R_3(T)\) | copies in upper CNF | base clauses | checked RUP additions |

|---|---:|---:|---:|---:|

| \(K_2\) | 2 | elementary | elementary | elementary |

| \(P_3\) | 5 | 30 | 131 | 3 |

| \(P_4\) | 6 | 180 | 601 | 85 |

| \(K_{1,3}\) | 8 | 280 | 953 | 105 |

| \(P_5\) | 9 | 7,560 | 22,825 | 5,033 |

| \(F_5\) | 9 | 7,560 | 22,825 | 4,762 |

| \(K_{1,4}\) | 11 | 2,310 | 7,151 | 2,161 |

Explicit nontrivial lower witness

One colouring of \(K_8\) simultaneously avoids \(P_5\) and \(F_5\). On

vertices \(0,\ldots,7\), its colour classes are

They partition all \(28\) edges. The verifier tests every injection of each

tree into each colour graph; neither tree occurs. Hence

All other lower witnesses, including colourings of \(K_4,K_5,K_7\), and

\(K_{10}\), are explicit edge lists in the standalone file and are checked

the same way.

Full upper encoding

For each edge \(e\in E(K_m)\) and colour \(c\in\{0,1,2\}\), the CNF has a

variable \(x_{e,c}\). It contains:

1. exactly-one-colour clauses for every edge;

2. for every injective copy \(\phi:T\hookrightarrow K_m\) and every colour

\(c\), the clause

\[ \bigvee_{uv\in E(T)}\neg x_{\phi(u)\phi(v),c}; \]

3. the safe symmetry break \(x_{01,0}\), since colours can always be renamed.

Thus the CNF is satisfiable exactly when \(K_m\) has a three-colouring with

no monochromatic \(T\). Duplicate edge-set copies are removed, but no

isomorphism or sampling assumption is made.

Glucose 4.2 generates a DRUP trace for each claimed-unsatisfiable upper

instance. The script then discards the solver verdict and checks the trace:

an added clause \(C\) is accepted only when unit propagation from the current

formula plus \(\{\neg\ell:\ell\in C\}\) reaches a conflict. The checker is a

separate pure-Python watched-literal implementation. Deletion records can

soundly be ignored, because retaining already proved clauses only strengthens

the formula. The final empty clause is explicitly required and checked.

This establishes each upper value computationally, rather than trusting an

opaque UNSAT string. It is still labelled (d), not promoted to an

elementary theorem.

Reproduction

Run:

python runs/erdos557_wave6b_reverify.py

The final clean run took 11.9 wall-seconds and printed:

Checking the exact R_3(T) table for every tree with 2 <= |T| <= 5
Unlabelled-tree census PASS (counts 1, 1, 2, 3)
K2: R_3=2 (the sole edge is monochromatic)
P3   : R_3= 5; K_4 witness PASS; K_5 UNSAT PASS (30 tree copies, 131 base clauses, 3 checked RUP additions, 0.00s)
P4   : R_3= 6; K_5 witness PASS; K_6 UNSAT PASS (180 tree copies, 601 base clauses, 85 checked RUP additions, 0.01s)
K1,3 : R_3= 8; K_7 witness PASS; K_8 UNSAT PASS (280 tree copies, 953 base clauses, 105 checked RUP additions, 0.01s)
P5   : R_3= 9; K_8 witness PASS; K_9 UNSAT PASS (7560 tree copies, 22825 base clauses, 5033 checked RUP additions, 6.30s)
fork5: R_3= 9; K_8 witness PASS; K_9 UNSAT PASS (7560 tree copies, 22825 base clauses, 4762 checked RUP additions, 4.87s)
K1,4 : R_3=11; K_10 witness PASS; K_11 UNSAT PASS (2310 tree copies, 7151 base clauses, 2161 checked RUP additions, 0.49s)
ALL CHECKS PASSED (11.67s in certified upper solves)

Claim ledger

• Live statement, status, comments, and markers: direct Bright Data page

extraction on 2026-07-27.

• Exact star formula (5): (a) elementary-rigorous; also matches the

named Burr–Roberts theorem.

• Extremal reduction (1)–(4): (a) elementary-rigorous.
• Bounded-degree bound \(R_q(T)\leq q(n-2)+2\): **(b)

rigorous-modulo-Pokrovskiy Theorem 1.16**.

• Uniform all-tree bound \(R_q(T)\leq qn+o(n)\): **(b)

rigorous-modulo-Davoodi et al. Corollary 1.6**.

• Exact \(R_3(T)\) table through five vertices: **(d) computational-only in

this report**, with explicit witnesses and checked RUP refutations.

• Claim that the additive all-tree step is presently missing:

literature-search diagnosis, not a theorem and not a priority claim.

PARTIAL: verified \(R_q(T)\leq q(n-2)+2\) for all sufficiently large fixed-bounded-degree trees (modulo Pokrovskiy Theorem 1.16), certified every \(R_3(T)\) for \(|T|\leq5\), and isolated the unresolved all-tree step as an additive-error embedding lemma beyond the current \(qn+o(n)\) theorem.