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

Erdős problem #612 — wave w002

Access date: 2026-07-28 UTC.

Claim labels used below:

(a) elementary-rigorous: proved directly here.
(b) rigorous-modulo-named-theorem: the named input is stated explicitly.
(c) plausible/structural-unverified: not used as a theorem.
(d) computational-only: an exhaustive finite calculation, with a standalone checker.

0. Mandatory live-page check

I fetched the live page and its LaTeX, history, and discussion views through the Bright Data browser path, not datacenter curl.

Live badge: OPEN.
Claimed proofs: 0.
“Currently working on this problem”: None.
“Interested in collaborating”: None.
There is one comment, by Adenwalla at 02:25 on 2026-02-12. It asks which

value of $r$ was intended if several values meet the first hypothesis, while acknowledging that that version has been disproved. The page warns that comments are unverified.

The page is not marked solved or falsified and has no current worker, so the

requested stop rule did not fire. The page does, however, explicitly say that the even-clique half of the displayed 1989 conjecture is disproved. I therefore treat the odd-clique half and the amended conjecture as the surviving targets.

Verbatim current statement

The following is copied from the live /latex/612 view:

Let $G$ be a connected graph with $n$ vertices, minimum degree $d$, and diameter $D$. Show if that $G$ contains no $K_{2r}$ and $(r-1)(3r+2)\mid d$ then\[D\leq \frac{2(r-1)(3r+2)}{2r^2-1}\frac{n}{d}+O(1),\]and if $G$ contains no $K_{2r+1}$ and $3r-1 \mid d$ then\[D\leq \frac{3r-1}{r}\frac{n}{d}+O(1).\]

Results listed on the page

The page attributes the problem and matching constructions to Erdős, Pach, Pollack, and Tuza, and says they proved $2r+1=3$. It also lists:

$D\le 3n/(d+1)+O(1)$ for arbitrary connected graphs.
Czabarka--Singgih--Székely's $K_{2r}$-free construction with

\[ D=\frac{6r-5}{(2r-1)d+2r-3}\,n+O(1), \] which disproves the even-clique clause for fixed $r\ge2$ and sufficiently large $d$.

Their amended conjecture: a connected $K_{k+1}$-free graph should satisfy

\[ D\le \left(3-\frac2k\right)\frac nd+O(1). \]

The amended bound under the stronger $k$-colourability hypothesis for

$k=3,4$.

Cambie--Jooken's $K_4$-free, $d=16$ lower bound

$D\ge(31/216)n+O(1)$, another counterexample to the original even-clique clause.

These are page reports, not assumptions silently added to the statement.

1. Primary-source literature check

(b) I checked the following primary sources and verified that the identifiers exist and contain the attributed statements.

P. Erdős, J. Pach, R. Pollack, Z. Tuza, *Radius, diameter, and minimum

degree*, JCTB 47 (1989), 73–79, DOI 10.1016/0095-8956(89)90066-X90066-X).

É. Czabarka, I. Singgih, L. A. Székely, *Counterexamples to a conjecture

of Erdős, Pach, Pollack and Tuza*, JCTB 151 (2021), 38–45, DOI 10.1016/j.jctb.2021.06.001. Its Theorem 3 gives the construction and formula quoted by the live page, and its Conjecture 2 is the amended conjecture.

É. Czabarka, P. Dankelmann, L. A. Székely, *Diameter of 4-colourable

graphs*, European J. Combin. 30 (2009), 1082–1089, DOI 10.1016/j.ejc.2008.09.005. It proves $D\le 5n/(2d)-1$ for connected 4-colourable graphs.

É. Czabarka, S. J. Smith, L. A. Székely, *Maximum diameter of 3- and

4-colorable graphs*, J. Graph Theory 102 (2023), 262–270, DOI 10.1002/jgt.22869, also arXiv:2109.13887.

S. Cambie, J. Jooken, *Sharp results for the Erdős, Pach, Pollack and

Tuza problem*, arXiv:2502.08626v1. The arXiv record has only v1, dated 2025-02-12. Its source contains the 31-column block checked below and says its full searches cost about one CPU-year. The associated public code is JorikJooken/diameterDegreeClique; the checked head was commit 426e38f692ab3efa071a3426c95f72e776a4ee75.

(c) Targeted title/formula/arXiv searches through 2026-07-28 found no later primary source resolving the $K_5$-free cases proved below. This is a search miss, not a proof of novelty. In particular, I do not claim bibliographic novelty as a theorem.

2. Main result: the first four $K_5$-free cases

Theorem

(b+d), computer-assisted. Let $G$ be a connected $K_5$-free graph of order $n$, minimum degree at least $\delta$, and diameter $D$. For the following values:

Consequently, for $\delta\in\{5,10,15,20\}$,

D\le \frac{5}{2\delta}n+O(1).

The coefficient is sharp. Thus the $r=2$ odd-clique clause of Problem #612 is established for its first four permitted minimum degrees. The $\delta=5$ case already follows from the general 1989 bound; the certified $\delta=10,15,20$ cases are the substantive additions.

The proof separates into an elementary finite reduction, Turán inequalities, and a completely enumerated potential certificate.

2.1 Layer cap

(a). For a fixed requested diameter $D_0$, take a minimum-order connected $K_5$-free graph $H$ of minimum degree at least $\delta$ and diameter at least $D_0$. Choose an endpoint $x$ of a diametral path and let

L_i=\{v:d(x,v)=i\},\qquad s_i=|L_i|,\qquad 0\le i\le D_H.

Edges occur only within one layer or between consecutive layers.

Every $s_i\le2\delta$. Otherwise replace $L_i$ by a $K_{\delta,\delta}$, join all its vertices to the adjacent layer(s), and delete edges internal to those adjacent layers. Then:

the order strictly decreases;
new middle vertices have at least $\delta$ neighbours in the opposite

bipartition, while adjacent-layer vertices have $2\delta$ new neighbours;

all other degrees are unchanged;
a clique meeting the replacement has size at most three;
the same nonempty layer chain remains, so $x$ still has the same

eccentricity.

This contradicts minimum order. Endpoint layers use the same one-sided replacement. Hence it is rigorous to enumerate only

1\le s_i\le2\delta.

This is the finiteness step; no unbounded-period assumption is being hidden.

2.2 Necessary local inequalities

Let four consecutive layer sizes be $a,b,c,d$, with middle layers $B,C$. Write $t_4(m)=\operatorname{ex}(m,K_5)$, the exact number of edges in the balanced complete 4-partite Turán graph.

The following are necessary.

(a) A vertex in the middle of $(a,b,c)$ has at most

$a+b+c-1$ possible neighbours, so \[ a+b+c\ge\delta+1. \tag{S1} \]

(b), Turán. $G[B]$ is $K_5$-free, hence it has a vertex of

internal degree at most $\lfloor3b/4\rfloor$. Therefore \[ a+c+\lfloor3b/4\rfloor\ge\delta. \tag{S2} \]

(b), Turán. Apply the same argument to $G[B\cup C]$. Its low-degree

vertex lies in $B$ or $C$, and can have outside neighbours only in the layer of size $a$ or $d$, respectively: \[ \max(a,d)+\left\lfloor\frac{3(b+c)}4\right\rfloor\ge\delta. \tag{T1} \]

(b), Turán degree sum. Every $B$-vertex has at least

$\max(0,\delta-a)$ neighbours in $B\cup C$, and every $C$-vertex has at least $\max(0,\delta-d)$. Hence \[ b\max(0,\delta-a)+c\max(0,\delta-d) \le 2t_4(b+c). \tag{T2} \]

(a+b). If $a+b+c=\delta+1$, every $B$-vertex is adjacent to every

other vertex in $A\cup B\cup C$. Thus $B$ is a clique, $b\le3$, and $G[C]$ is $K_{5-b}$-free. Turán applied inside $C$ gives \[ b+d+\left\lfloor\frac{(3-b)c}{4-b}\right\rfloor\ge\delta. \tag{T3} \] The reflected condition is imposed when $b+c+d=\delta+1$.

These tests discard some impossible size sequences but deliberately retain many non-realizable ones. That only makes the final upper bound stronger.

2.3 Finite potential certificate

(d). For a fixed $\delta$, make a directed state graph:

vertices are triples $(a,b,c)\in[1,2\delta]^3$ satisfying (S1),(S2);
$(a,b,c)\to(b,c,d)$ exactly when the next state and (T1)–(T3), including

the reflected test, hold;

the edge cost is $d-m$, where $m=2\delta/5$.

The verifier constructs an integer potential $h$ and checks on every edge

h(b,c,d)\le h(a,b,c)+d-m. \tag{P}

This is a checkable certificate, not an optimizer's unsupported answer. Summing (P) around any directed cycle proves that its mean layer size is at least $m$. More importantly, summing it along an arbitrary finite BFS layer sequence telescopes.

The exact certificates are:

| $\delta$ | states | transitions | $\min h$ | SHA-256 of sorted $h$ table | |---:|---:|---:|---:|---| | 5 | 990 | 9,798 | -2 | 5211f3b457c2c736bd15c82e5f39c2f947394a9d46e61635fdecd25362b5e75b | | 10 | 7,862 | 154,754 | -6 | b9c55a956a876e2b599d4774e2382d37929f4e5490477da35e7aac69d443bd2a | | 15 | 26,451 | 779,525 | -10 | 2d9440c48fcb738af427cda6a8db13f263314f1cb8e05ca4c2400c4a0beff9e8 | | 20 | 62,590 | 2,456,918 | -14 | 5752f8b6794c998c1d961f9ead9feaba9c9f50305238ebee728f8d2cee810f26 |

For $u_i=(s_{i-1},s_i,s_{i+1})$, sum (P) from $i=1$ to $D_H-2$:

\sum_{j=3}^{D_H}(s_j-m) \ge h(u_{D_H-1})-h(u_1)\ge \min h.

Also $s_0=1$, $s_1\ge\delta$, and $s_2\ge1$. Substitution of the four certified minima gives exactly the four inequalities in the theorem. For $D_H\le2$, $n\ge\delta+1$ makes the listed bounds immediate. Finally, $|V(G)|\ge|V(H)|$ and $D_H\ge D_0$, so the result applies to every original graph, not merely a repeatable or bounded-diameter graph.

2.4 Sharp construction

(a). Let $\delta=5t$. Alternate two kinds of layers:

(t,t,0,0),\qquad(0,0,t,t),

where the entries are four colour-class sizes. Join all differently coloured vertices in the same or consecutive layers. Every interior vertex has

t+2t+2t=5t=\delta

neighbours, and the displayed four-colouring certifies $K_5$-freeness.

Take $2q$ layers and cap each end with a $K_{\delta,\delta}$, joining one side of each cap to the boundary layer with unused colours. The resulting finite graph has

n=4qt+4\delta,\qquad D=2q+3,

and hence, with $m=2\delta/5=2t$,

D=\frac{n}{m}-7=\frac{5n}{2\delta}-7.

Thus the upper coefficients in the table are asymptotically sharp. The standalone program explicitly builds capped examples and recomputes every degree, colour conflict, connected component, and all-pairs diameter.

3. Explicit verification of the published even-case counterexample

This section is not new progress; it independently makes the live page's Cambie--Jooken lower bound fully reproducible.

Their three-colour block is the following $3\times31$ matrix of colour-class sizes:

0 0 7 0 1 0 7 0 0 7 0 0 2 5 0 0 7 0 0 4 3 0 0 7 0 0 8 0 1 0 7
0 1 0 8 0 7 0 2 0 7 0 2 0 7 0 4 0 5 0 7 0 2 0 7 0 2 0 7 0 0 8
2 0 7 0 1 0 7 0 2 0 7 0 7 0 2 0 7 0 2 0 7 0 6 0 3 0 5 2 0 7 0

(a). Join differently coloured vertices in the same or consecutive layers. Direct recomputation gives:

period $31$;
total block weight $66+76+74=216$;
every occupied colour class has weighted degree $16$ or $17$;
a proper 3-colouring, hence no $K_4$;
$31/216-1/7=1/1512>0$.

Scale all entries by $t$, repeat the block $q$ times, and cap the two ends by $K_{16t,16t}$. The checker constructs a finite graph with

n=t(216q+64),\qquad \delta=16t,\qquad D=31q+3.

For the original $r=2$ even-clique prediction, the leading term is $n/(7t)$, and exactly

D-\frac{n}{7t}=\frac{q-43}{7}.

The excess is unbounded with $q$, so no additive $O(1)$ can repair that clause.

4. Code and reproduced output

The complete standard-library verifier is runs/erdos612_wavew002_verify.py. Its core certificate check is:

for state in states:
    potential[state] = 0

while True:
    updates = 0
    for a, b, c in states:
        old = potential[a, b, c]
        for d in range(1, 2 * delta + 1):
            if transition_valid(delta, a, b, c, d):
                candidate = old + d - 2 * delta // 5
                if potential[b, c, d] > candidate:
                    potential[b, c, d] = candidate
                    updates += 1
    if updates == 0:
        break

for a, b, c in states:
    for d in range(1, 2 * delta + 1):
        if transition_valid(delta, a, b, c, d):
            assert (
                potential[b, c, d]
                <= potential[a, b, c] + d - 2 * delta // 5
            )

Command:

python runs/erdos612_wavew002_verify.py

Reproduced output:

Cambie--Jooken block: period=31 weight=216 degrees={16,17} slope_gap=1/1512; capped graphs checked
Sharp K_5-free families checked for delta={5,10,15,20}: D=n/(2 delta/5)-7
delta=5 potential: states=990 transitions=9798 range=[-2,0] sha256=5211f3b457c2c736bd15c82e5f39c2f947394a9d46e61635fdecd25362b5e75b
  certified consequence: n >= 2D+1
delta=10 potential: states=7862 transitions=154754 range=[-6,0] sha256=b9c55a956a876e2b599d4774e2382d37929f4e5490477da35e7aac69d443bd2a
  certified consequence: n >= 4D-2
delta=15 potential: states=26451 transitions=779525 range=[-10,0] sha256=2d9440c48fcb738af427cda6a8db13f263314f1cb8e05ca4c2400c4a0beff9e8
  certified consequence: n >= 6D-5
delta=20 potential: states=62590 transitions=2456918 range=[-14,0] sha256=5752f8b6794c998c1d961f9ead9feaba9c9f50305238ebee728f8d2cee810f26
  certified consequence: n >= 8D-8
ALL CHECKS PASSED

The run took about 72 seconds wall time on this VM, using one Python process.

5. Exact remaining wall

The original displayed problem is not closed:

its even-clique half is already false;
the argument here settles only $r=2$ and

$d\in\{5,10,15,20\}$ in the odd-clique half;

$r=2$ at $d=25,30,\ldots$, all $r\ge3$, and the general amended

$K_{k+1}$-free conjecture remain.

(c). For the four verified certificates, $\min h=2-2m$, where $m=2\delta/5$. This pattern suggests that an analytic potential valid for all multiples of five may exist, but four data points are not a uniform proof.

The exact missing step for all $r=2$ is either:

give a closed formula $h_\delta(a,b,c)$ satisfying (P) for every

$\delta\equiv0\pmod5$; or

prove a finite list of stronger local $K_5$-free inequalities from which

such a potential follows uniformly.

A naïve next computation at $\delta=25$ has up to $50^3=125{,}000$ states and $50^4=6.25$ million candidate transitions. Streaming them avoids the large edge-list memory cost, but multiple relaxation sweeps would cost roughly 2–5 core-minutes in the present pure-Python implementation. I did not run that heavier case because another isolated certificate would still not supply the uniform lemma.

For $r\ge3$, the analogous target mean layer size is $rd/(3r-1)$. The $2d$ layer cap still gives finiteness for each fixed case, but the local Turán and “tight triple” rules must be replaced by $K_{2r+1}$-free versions. A uniform potential or a genuinely new local stability lemma is the precise mathematical bottleneck.

PARTIAL: proved the sharp $K_5$-free odd-clique bound for $d=5,10,15,20$, with uniform-in-diameter finite certificates and a standalone verifier; the general problem remains open.

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