Erdős problem #934 — wave 7u

Access/research date: 2026-07-28 UTC.

Claim labels used throughout:

• [a] elementary-rigorous — proved here from definitions;
• [b] rigorous-modulo-named-theorem — the deduction is rigorous assuming the explicitly named published/preprint theorem;
• [c] plausible/structural-unverified;
• [d] computational-only — exhaustively checked by the standalone deterministic program.

No claim below is labelled [c].

0. Mandatory live-page audit

I fetched both the problem page and its discussion thread through the Bright Data browser route:

• <https://www.erdosproblems.com/934>
• <https://www.erdosproblems.com/forum/discuss/934>

The direct live-page findings were:

• Status: OPEN.
• Claimed proofs: 0.
• “Currently working on this problem”: None.
• “Interested in collaborating”: None.
• “Likes this problem”: woutercvb.
• All “looks difficult”, “looks tractable”, and formalisation worker markers: None.
• The page says it was last edited 28 October 2025, although its discussion has comments from March 2026.

Thus the mandatory stop condition was not triggered.

Verbatim current statement

> Let \(h_t(d)\) be minimal such that every graph \(G\) with \(h_t(d)\) edges and maximal degree \(\le d\) contains two edges whose shortest path between them has length \(\ge t\).

>

> Estimate \(h_t(d)\).

Results listed on the live page

The page attributes the problem to Erdős and Nešetřil and records:

1. \(h_t(d)\le 2d^t\), and the displayed text says \(h_1(d)=d+1\).

2. Erdős–Nešetřil and Bermond–Bond–Paoli–Peyrat conjectured

\(h_2(d)\le \frac54d^2+1\), with equality for even \(d\); Chung–Gyárfás–Tuza–Trotter proved it.

3. Cambie–Cames van Batenburg–de Joannis de Verclos–Kang (CCJK) conjectured

\[ h_3(d)\le d^3-d^2+d+2, \]

with equality exactly when \(d=p^k+1\), and proved \(h_3(3)=23\).

4. CCJK also conjectured, for each \(t\ge3\), lower examples

\((1-o(1))d^t\) for infinitely many \(d\), and a uniform upper bound

\((1+o(1))d^t\).

5. CCJK proved \(h_t(d)\le\frac32d^t+1\), and for large \(t\) constructed infinitely many \(d\) with \(h_t(d)\ge0.629^t d^t\).

These are faithful transcriptions of what the page lists, not an assertion that the list is current.

All three live comments

1. Adenwalla, 24 March 2026, asks whether \(K_3\) contradicts \(h_1(2)=3\).

2. Thomas Bloom, 25 March 2026, agrees: the displayed formula is valid for \(d\ge3\), while \(K_3\) is the exceptional obstruction at \(d=2\).

3. StijnC, 25 March 2026, says the intended assumption was \(d\ge3\), states

\(h_t(2)=2t+2\), and sketches the pairwise-incident-edge argument for \(h_1(d)=d+1\) when \(d\ge3\).

The site explicitly warns that comments are user-supplied and unverified. I give an independent proof of the degree-two formula below.

1. Exact reformulation

For distinct edges \(e,f\), let

Then

Consequently, if

then

This is exactly the equivalence used in both the 2022 and 2026 primary sources. [a]

Thus the \(t=3\) problem asks how many edges a maximum-degree-\(d\) graph can have when every two vertices of its line graph are at distance at most three.

2. Literature audit and the material 2026 update

Primary sources verified

1. Erdős (1988). Paul Erdős, “Problems and results in combinatorial analysis and graph theory,” Discrete Mathematics 72 (1988), 81–92, DOI

10.1016/0012-365X(88)90196-390196-3).

The source PDF contains the \(h_t\) question and says its order is \(d^t\), while asking for a “nice expression.” [b]

2. Chung–Gyárfás–Tuza–Trotter (1990). “The maximum number of edges in \(2K_2\)-free graphs of bounded degree,” Discrete Mathematics 81 (1990), 129–135, DOI

10.1016/0012-365X(90)90144-790144-7).

Its abstract gives maximum edge count \(5d^2/4\) for even \(d\), and

\((5d^2-2d+1)/4\) for odd \(d\). Via (1), this is the stated \(h_2\) result. [b]

3. CCJK (2022). Stijn Cambie, Wouter Cames van Batenburg, Rémi de Joannis de Verclos, and Ross J. Kang, “Maximizing Line Subgraphs of Diameter at Most \(t\),” SIAM J. Discrete Math. 36 (2022), 939–950, DOI

10.1137/21M1437354, preprint

arXiv:2103.11898v2.

The PDF states Theorem 2, \(h_3(3)=23\), and Theorem 6,

\(h_t(d)\le\frac32d^t+1\), and contains the two conjectures quoted by the live page. [b]

4. Kumar–Mohar–Pragada (2026). Hitesh Kumar, Bojan Mohar, and Shivaramakrishna Pragada, “An improved bound for the strong clique index of graphs,”

arXiv:2607.02698v1, submitted 2 July 2026.

Section 3 explicitly disproves both CCJK \(t=3\) conjectures. It gives the Odd graph \(O_4\), the truncated Witt graph, a projective-plane lift, and

\[ \liminf_{d\to\infty}\frac{h_3(d)}{d^3}\ge\frac{253}{225}. \tag{2} \]

It asks whether \(h_3(d)\le\frac{253}{225}d^3\) for all sufficiently large \(d\), and says the CCJK asymptotic upper conjecture remains undecided for \(t\ge4\). [b]

The last paper postdates the live page’s stated last-edit date and is not listed there. It does not solve the general Erdős problem, so the live OPEN status is consistent, but it makes both \(t=3\) conjectures displayed on the page false.

Search coverage and honest misses

• Exact-phrase arXiv API searches for “line subgraphs of diameter” and “edge-version of the degree-diameter” returned only arXiv:2103.11898 and arXiv:2607.02698.
• An OpenAlex citation query for DOI 10.1137/21M1437354 returned a 2023 graph-squares survey and Aida Abiad–Harper Reijnders, “Eigenvalue bounds for distance-edge colorings,” arXiv:2506.20976. I inspected the latter PDF: it studies the chromatic parameter \(\chi'_t(G)\), cites the CCJK coloring bound, and does not state a new extremal bound for \(h_t(d)\).
• Because the Kumar–Mohar–Pragada preprint is only weeks old, citation indexes did not yet return it; exact web/arXiv searching did.

This search cannot prove that no other paper exists. It records exactly what was found and checked.

3. First explicit counterexample: \(O_4=KG(7,3)\)

Let the vertices be the \(3\)-subsets of \([7]\), with two vertices adjacent exactly when the corresponding sets are disjoint.

• There are \(\binom73=35\) vertices.
• Each vertex has \(\binom43=4\) disjoint \(3\)-sets.
• Hence there are \(35\cdot4/2=70\) edges.

Take two graph edges \(AB\) and \(CD\). Thus \(A\cap B=C\cap D=\varnothing\), and both \(A\cup B\) and \(C\cup D\) have size six. Therefore

The four pairwise-disjoint sets \(A\cap C,A\cap D,B\cap C,B\cap D\) partition this intersection, so one has size at least two. Choose corresponding endpoints \(U\in\{A,B\}\) and \(V\in\{C,D\}\).

• If \(|U\cap V|=3\), then \(U=V\), so the original edges are incident.
• If \(|U\cap V|=2\), the complement \(X=[7]\setminus(U\cup V)\) is a \(3\)-set disjoint from both \(U\) and \(V\). Thus

\[ AB,\ UX,\ XV,\ CD \]

is a walk of length at most three in the line graph.

Therefore \(\operatorname{diam}L(O_4)\le3\), and (1) yields

But the old conjectured upper value was

So \(O_4\) is a \(17\)-unit contradiction to that proposed bound. [a]

The checker independently finds the exact line-distance histogram among all

\(\binom{70}{2}=2415\) edge pairs:

[d]

Combining (3) with the CCJK upper theorem gives the currently verified finite interval

The lower endpoint is [a]; the upper endpoint is [b].

4. Stronger explicit base: the truncated Witt graph

The companion program defines, rather than downloads, the graph.

1. Over \(\mathbf F_2\), set

\[ g(x)=x^{11}+x^9+x^7+x^6+x^5+x+1. \]

2. Enumerate the \(4096\) products \(m(x)g(x)\), \(\deg m<12\), and append an overall parity coordinate.

3. Extract the supports of the weight-eight words.

The program verifies:

• the complete weight enumerator

\[ 1+759z^8+2576z^{12}+759z^{16}+z^{24}; \]

• exactly \(759\) weight-eight supports (“octads”);
• every one of the \(\binom{24}{5}=42504\) five-subsets occurs in exactly one octad, so the generated blocks form \(S(5,8,24)\);
• distinct octads intersect in \(0,2,\) or \(4\) points.

Fix coordinate \(0\) and retain the octads avoiding it. Join two retained octads when they are disjoint. The program obtains a connected graph \(W\) with

It then checks all

edge pairs. Their exact line-distance histogram is

In particular, \(\operatorname{diam}L(W)=3\), so

All finite assertions in this section are [d]. The implication from the audited graph to (5) is [a].

For reproducibility, the canonical truncated-Witt edge-list SHA-256 printed by the checker is

3e8d52ab04789df876a04137654603313099331a189cd09dc3882cddb1ef6632.

5. Projective-plane lift and a fully numerical counterexample

Here is the elementary lifting lemma underlying the 2026 preprint.

Let \(H\) be an \(r\)-regular graph with \(\operatorname{diam}L(H)\le3\), and let \(q\) be a prime power. Let \(P=\operatorname{PG}(2,q)\). Define \(G[H,q]\) on

by joining \((u,\alpha)\) to \((v,\beta)\) exactly when \(uv\in E(H)\) and

\(\alpha\cdot\beta=0\).

Every polar line \(\alpha^\perp\) has \(q+1\) points, so

To check the diameter, project two lifted edges to two edges of \(H\).

A shortest line-graph walk of length at most three supplies endpoints \(u,v\) that are equal or have a common neighbor \(p\). If their lifted coordinates are \(\alpha,\beta\), the two projective lines \(\alpha^\perp,\beta^\perp\) meet in some \(\gamma\). Hence

so the lifted edges are at line-graph distance at most three. Thus

The lemma and formulas (6) are [a].

The checker constructs all \(57\) canonical points of \(\operatorname{PG}(2,7)\), verifies that every polar line has eight points, and checks that every pair of polar lines meets. It combines this with the exhaustive connector audit of \(W\). Therefore \(G[W,7]\) has

Consequently,

The old conjectured upper value is

so (7) exceeds it by exactly \(16{,}799\). The lift is [a] conditional on the base audit; the explicit \(W\) instance is [d].

For general prime \(q\), divide (6) by \([15(q+1)]^3\):

The prime number theorem supplies a prime \(q=(1-o(1))d/15\) below \(d/15\); monotonicity of \(h_3(d)\) then upgrades the prime subsequence to (2). This deduction is [b], with the finite base property [d].

Thus the now-verified \(t=3\) asymptotic window is

The lower inequality is [b]+[d]; the upper inequality is [b] from CCJK.

6. Exact boundary regime \(d\le2\)

Degree one

A maximum-degree-one graph with two edges has those edges in different components, hence their distance is infinite. One edge avoids the condition. Therefore

[a]

Degree two

If a graph avoiding two edges at distance at least \(t\) had edges in two components, those edges would be at infinite distance. Hence all its edges lie in one connected component. A connected finite simple graph of maximum degree at most two is a path or a cycle.

• A path with \(m\) edges has line graph \(P_m\), of diameter \(m-1\), so \(m\le t+1\).
• A cycle with \(m\) edges has line graph \(C_m\), of diameter \(\lfloor m/2\rfloor\), so \(m\le2t+1\).

The cycle \(C_{2t+1}\) attains the latter value. By (1),

[a]

In particular \(h_1(2)=4\), explaining the live comments. More generally, a family of pairwise incident edges in a simple graph is a star or a triangle, so

[a]

7. What remains, precisely

The general problem is not closed.

• For \(t=3\), the exact missing uniform statement is an upper theorem for every graph \(G\) with \(\Delta(G)\le d\) and \(\operatorname{diam}L(G)\le3\). The sharp candidate proposed in arXiv:2607.02698 is

\[ |E(G)|\le\frac{253}{225}d^3-1 \]

for all sufficiently large \(d\), or an asymptotic variant with \(o(d^3)\). Existing CCJK machinery stops at \(\frac32d^3\); the gap in (8) is real.

• Exact \(h_3(4)\) still requires eliminating or constructing graphs in the \(26\)-integer gap (4). The \(C_7\)-free theorem from CCJK cannot do this because \(O_4\) itself lies beyond the generalized-polygon bound; controlling the allowed \(7\)-cycles is the missing structural ingredient.
• For \(t\ge4\), Kumar–Mohar–Pragada explicitly leave the CCJK \((1+o(1))d^t\) upper conjecture undecided. Their projective lift is intrinsically a line-diameter-three mechanism and does not automatically propagate a counterexample to larger \(t\).

These are theorem gaps, not evidence that the desired bounds are “probably” true.

8. Reproduction

Complete standalone source:

It uses only the Python standard library and performs no network access. Run:

python runs/erdos934_wave7u_reverify.py

Observed output:

Erdos #934 deterministic re-verification
==========================================
O4: |V|=35, Delta=4, |E|=70
O4 edge-pair distances: {1: 210, 2: 630, 3: 1575}
O4 block SHA256: 83359200a3c5384c431b0da8808658b6e19d773e561ec065733c92cc91c895a1
O4 edge SHA256: 7defdd70dddf89e0652edf5d5746fea59fdcce3898ef927e6596b1d38b720002
Golay weight enumerator: {0: 1, 8: 759, 12: 2576, 16: 759, 24: 1}
Octad SHA256: fe5f7e307dee686f9c8c5d0c5e5d89d38c816b7c82b99dfea3ec407e6a537763
Truncated-octad SHA256: e3c4fe6fd07142f61a76f5ca59bf443b9cff1a13c26563f7841ae54ce27a75c7
Truncated-Witt edge SHA256: 3e8d52ab04789df876a04137654603313099331a189cd09dc3882cddb1ef6632
Truncated-Witt edge-pair distances: {1: 53130, 2: 743820, 3: 6402165}
G[W,7]: |V|=28842, Delta=120, |E|=1730520
Finite consequence: h_3(120) >= 1730521 > 1713722 (old conjectured upper), gap 16799
Witt-lift base ratio: 253/225 = 1.124444444444
Finite consequence: h_3(4) >= 71 > 54 (old conjectured upper)
Exact degree-two table (t, h_t(2)): [(1, 4), (2, 6), (3, 8), (4, 10), (5, 12), (6, 14), (7, 16), (8, 18)]
ALL CHECKS PASSED

The verifier itself has SHA-256

f41ef64824742128bba91e5be6b49d801414c32e5a286f6379d900fb0636f12c.

PARTIAL: verified the July-2026 disproofs from explicit Odd/Witt constructions, certified h_3(4)>=71 and h_3(120)>=1,730,521, proved h_t(2)=2t+2, and isolated the remaining 253/225-versus-3/2 t=3 gap.