Erdős problem 809 — wave 6l

Date: 2026-07-27 UTC

Outcome: the live problem is still open, with no claimed proof and no current

worker. The unresolved asymptotic case is \(C_7\). I did not solve that

case uniformly, but obtained and independently rechecked the exact first

nontrivial finite value

I use the requested claim labels throughout:

• [a] elementary-rigorous;
• [b] rigorous modulo the named source/theorem;
• [c] plausible or structural but unverified;
• [d] computational-only.

0. Mandatory live-page gate

[b] I accessed the Cloudflare-protected live page and its discussion with

the Bright Data browser on 2026-07-27:

• problem 809;
• LaTeX view;
• discussion thread.

The live page reported:

• status OPEN;
• 0 claimed proofs;
• Currently working: None;
• Interested in collaborating: None;
• one comment, by Alfaiz at 06:30 on 20 March 2026, pointing out the

Bucić–Chen–Ma result for \(k\geq4\); the comment says the site was updated;

• last page edit: 1 April 2026.

Thus the mandatory stop condition was absent.

Exact current statement

To keep the mathematical content exact, here is a formal transcription of the

definition in the live LaTeX view:

The exact question line on the live page is:

> Is it true that, for all \(k\geq 3\),

> \[ > \chi_S(n,\lfloor n^2/4\rfloor+1,C_{2k+1})\sim n^2/8? > \]

[b] The same live page lists the following known results:

from Burr–Erdős–Graham–Sós; the conjectured asymptotic is now proved for

every \(k\geq4\) by Bucić–Chen–Ma; and the page contrasts this with

and, for all large \(n\),

Consequently, [b] only \(k=3\), namely the target \(C_7\), remains from

the displayed conjecture.

1. Primary-source literature audit

[b] I verified the following sources rather than relying on search-result

summaries.

1. S. A. Burr, P. Erdős, R. L. Graham, and V. T. Sós,

Maximal antiramsey graphs and the strong chromatic number,

J. Graph Theory 13 (1989), 263–282,

DOI,

official Erdős archive scan.

Section 5, especially journal page 270, proves a quadratic lower bound for

every fixed odd cycle of length at least seven. It treats \(C_7\)

separately inside that proof and then asks whether the leading constant can

be \(1/8\).

2. M. Bucić, K. Chen, and J. Ma,

On a maximal anti-Ramsey conjecture of Burr, Erdős, Graham, and Sós,

arXiv:2603.18952 (2026).

Theorem 1.2 proves, for fixed \(k\geq4\) and throughout the nontrivial edge

range,

\[ f(n,e,C_{2k+1}) =\frac e2+\frac n2\sqrt{e-\frac{n^2}{4}}+o(n^2). \]

On PDF page 11, immediately after the proof, the authors explain that

\(k\geq4\) is needed for their short-path length budget. They say that a

more involved stability argument handles their second (near-Turán) case for

\(k=3\), while their first (higher-density) case remains the bottleneck.

3. [b] The live page cites P. Erdős,

*Problems and results in combinatorial analysis and combinatorial number

theory*, Graph Theory, Combinatorics, and Applications, Vol. 1 (1991),

397–406, at page 398. I verified the bibliographic record and that it is

the source attached to problem 809; I did not find an independently

accessible primary scan during this run.

[b] Targeted web/arXiv searches for the exact maximal anti-Ramsey \(C_7\)

case, for papers citing arXiv:2603.18952, and for 2026 follow-ups found the

Bucić–Chen–Ma paper and unrelated new work on \(P_4\), but no later primary

source resolving \(C_7\). This is an honest search miss, not a proof that no

such source exists.

2. Exact reduction used by the computation

For a fixed host graph \(H\), define its \(C_7\)-edge-conflict graph \(Q_7(H)\)

as follows:

[a] Lemma.

An edge-colouring of \(H\) makes every \(C_7\) rainbow if and only if it is a

proper vertex-colouring of \(Q_7(H)\). Hence

Proof.

Every \(C_7\) is rainbow exactly when every pair among its seven edges has

different colours. Those and only those pairs are edges of \(Q_7(H)\).

This turns the finite problem into an ordinary exact chromatic problem and,

for a lower bound, it suffices to find a clique in every \(Q_7(H)\).

3. Exact finite result

3.1 Table

The verified table at the problem's prescribed edge count is:

| \(n\) | \(\lfloor n^2/4\rfloor+1\) | \(\chi_S(n,\lfloor n^2/4\rfloor+1,C_7)\) | status |

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

| 3 | 3 | 1 | [a] |

| 4 | 5 | 1 | [a] |

| 5 | 7 | 1 | [a] |

| 6 | 10 | 1 | [a] |

| 7 | 13 | 1 | [a] |

| 8 | 17 | 1 | [a] |

| 9 | 21 | 1 | [a] |

| 10 | 26 | 13 | [d] |

For \(n=1,2\), the prescribed edge count exceeds \(\binom n2\), so I do not

assign a value.

3.2 Elementary \(n\leq9\) witnesses

[a] For \(3\leq n\leq6\), no graph has a \(C_7\), so any host at the

required edge count can be coloured with one colour.

[a] For \(n=7\), take any 13 edges inside a fixed six-vertex set and leave

the seventh vertex isolated.

[a] For \(n=8\), take \(K_6\), an edge on the other two vertices, and one

bridge joining these pieces. This has \(15+1+1=17\) edges, and every cycle is

contained in a block of order at most six.

[a] For \(n=9\), take

It has \(3+3\cdot6=21\) edges. Independent-set vertices cannot be consecutive

on a cycle, so a \(C_7\) would require at least four vertices from the

three-vertex clique, which is impossible.

In every case the one-colour lower bound is tautological, so the value is

exactly one. The verifier reconstructs each host and enumerates its \(C_7\)'s

from scratch.

3.3 Explicit 13-colour witness for \(n=10\)

Let

put on \(A\) the paw with edges

put on \(B\) the diamond \(K_4-12\), with edges

and join two further adjacent vertices \(8,9\) to every vertex of

\(A\cup B\). Thus

has

edges.

Use colours as follows:

• give the nine paw/diamond edges distinct colours \(0,\ldots,8\), in the

order

\[ 04,15,25,16,26,56,07,37,47; \]

• colour \(8A\) with colour 9 and \(8B\) with colour 10;
• colour \(9A\) with colour 11 and \(9B\) with colour 12;
• colour \(89\) with colour 0.

[a] This is a valid 13-colouring. Indeed, a \(C_7\) cannot use \(89\):

an alternative \(8\)-to-\(9\) path of length six would need five distinct

vertices inside one of the two four-vertex components. A \(C_7\) also cannot

use only one of \(8,9\), since deleting that hub leaves a path inside one

four-vertex component. Therefore every \(C_7\) uses both hubs but not \(89\).

The two base paths between the hubs cannot both lie in the same four-vertex

component, because together they use five base vertices. Hence at each hub

the cycle uses at most one spoke from each same-colour component class. All

base edges already have distinct colours, proving the claim.

For machine-independent identification, this host has graph6 string

I?`bKr~~w

and the standalone checker lists all 26 edges and all 26 colour values.

3.4 Exhaustive lower bound

[d] Computational theorem.

Every simple 10-vertex graph \(H\) with 26 edges has a clique \(K_{13}\) in

\(Q_7(H)\). Consequently every rainbow-\(C_7\) colouring of \(H\) needs at

least 13 colours.

The exhaustive check did the following.

1. nauty-geng 2.8.8 generated one graph6 representative of every unlabelled

10-vertex graph with exactly 26 edges. There were exactly 828,728 records.

The generated byte stream had SHA-256

ded24c07f48b643935965874833ecbe1fc443481b814917571e72f30740aac77.

2. A separate C++20 scanner decoded graph6 itself.

3. For every host it enumerated all simple 7-cycles by DFS. The least cycle

vertex was fixed as the start and one of the two orientations was retained,

so every unoriented \(C_7\) appeared exactly once.

4. Each cycle made its seven host-edge indices a clique in \(Q_7(H)\).

5. A bitset branch-and-bound search found a \(K_{13}\). On every successful

host the returned 13-bit certificate was separately checked pairwise

against the constructed conflict graph.

Because \(\chi(Q_7(H))\) is invariant under relabelling, one representative of

each isomorphism class is sufficient. The dependence on nauty's exhaustive

unlabelled generation is why this result is marked [d], not [a].

The final scan output was:

explicit C7-free hosts: PASS (chi_S=1 for 3 <= n <= 9)
n=10 witness: PASS (26 edges, 292 C7s, 276 conflicts, K13 and 13-coloring)
exhaustive lower bound: PASS (828728 unlabelled hosts; every Q7(G) contains K13; graph6 SHA256=ded24c07f48b643935965874833ecbe1fc443481b814917571e72f30740aac77, matches recorded digest)
FINAL CHECK: chi_S(10,26,C7)=13 (computational-only)

For the explicit host \(H_0\), two structurally independent Python cycle

enumerators—DFS and iteration over all 7-subsets and cyclic permutations—both

found exactly 292 cycles and the same cycle set. They produced a conflict

graph with 276 edges. The following 13 host edges were independently checked

to form a conflict clique:

Together with the explicit 13-colouring, this also certifies

\(\chi(Q_7(H_0))=13\).

[d] Corollary.

\(\operatorname{ex}(10,C_7)=25\): the exhaustive \(K_{13}\) result forces a

\(C_7\) at 26 edges, while \(K_{5,5}\) is a 25-edge \(C_7\)-free graph.

4. Reproduction code

The entry point is:

python runs/erdos809_wave6l_verify.py

It compiles and invokes the transparent C++ scanner automatically. Required

local programs are Python 3.12+, g++ with C++20, and nauty-geng.

On this VM the full run took about 35 seconds. A fast construction-only check

is:

python runs/erdos809_wave6l_verify.py --quick

Files:

• runs/erdos809_wave6l_verify.py — standalone re-verification entry point,

graph6 cross-check, two independent cycle enumerators, explicit witnesses,

colouring/clique checks, generator checksum, and exhaustive-scan driver;

• runs/erdos809_wave6l_scan.cpp — auditable exhaustive conflict-graph and

clique scanner compiled by the Python entry point.

The core checked equivalence is implemented literally:

for cycle in cycles:
    edge_ids = [index[cycle_edge] for cycle_edge in cycle]
    for u, v in combinations(edge_ids, 2):
        conflict[u].add(v)
        conflict[v].add(u)

and the lower-bound scanner accepts a host only after it has found and then

pairwise rechecked 13 mutually conflicting host edges.

5. What remains and the precise wall

[b] In the Bucić–Chen–Ma higher-density case, two selected “good” edges

are joined using a path \(P_1\) of length at most three, a filler of length

and a closing path of length four. For \(k=3\), the filler length becomes

which is negative as soon as \(\ell(P_1)\geq2\). This is the exact numerical

failure of that proof template, not merely a vague loss in constants.

[c] A sufficient missing lemma within their template would be a

higher-density structural statement producing the required number

of edges that are pairwise co-contained in \(C_7\), or a replacement

colour-counting argument of the same strength that does not demand pairwise

co-containment. Their present distance-\(\leq3\) and exact-length-4 path

lemmas do not supply the necessary \(C_7\) length budget. I do not claim

that the stronger pairwise lemma is true; it precisely identifies what would

make the existing induction close.

[d] Extending only the finite table to \(n=11\) is already outside the

few-CPU-minute budget. nauty-geng -u 11 31:31 counted 70,065,437 unlabelled

hosts in 25.9 CPU-seconds. At the measured \(n=10\) scanner rate, even before

allowing for the larger cycle/conflict graphs, a corresponding scan costs

about 0.8 core-hours; a realistic allowance is 0.8–1.5 core-hours

(roughly USD 0.08–0.15 at USD 0.10 per vCPU-hour). Such a scan would still

give only another finite value and cannot supply the uniformity needed for the

asymptotic problem.

PARTIAL: The live problem remains open only for C7; exact computation and an explicit certified witness give chi_S(10,26,C7)=13, while the uniform high-density path-length lemma needed for the n→∞ asymptotic is still missing.