Erdős Problem #619

Erdős Problem 619: the diameter-four conjecture fails

Statement and current resolution

For a connected triangle-free graph $G$ on $n$ vertices, let $h_4(G)$ be the minimum number of edges that must be added, preserving triangle-freeness, to obtain diameter at most four. The proposed bound was $h_4(G)\le(1-\varepsilon)n$ for some absolute $\varepsilon>0$. The answer is negative. This attempt reconstructs the pendant-vertex counterexample described by Nick Kuhn in the problem's discussion and associated proof repository. The proof below supplies an elementary random construction of the required core and proves the qualitative counterexample for every fixed $\varepsilon$. It does not claim the sharper error term reported in that work.

1. Sparse cores with small independence ratio

For every sufficiently large fixed integer $d$, there are arbitrarily large connected triangle-free graphs $H$ with $m$ vertices satisfying \[ \Delta(H)\le D:=2d+2,\qquad \alpha(H)\le\rho m,\quad \rho:=8\log d/d. \tag{1} \] Here is a proof. In a random graph on $M$ vertices with edge probability $d/M$, the exponential Markov inequality gives \[ \Pr(\deg(v)\ge2d)\le\frac{\mathbb E2^{\deg(v)}}{2^{2d}} \le(e/4)^d. \] Thus with probability at least $1-10(e/4)^d$, at most $M/10$ vertices have degree at least $2d$. The expected number of triangles is at most $d^3/6$, so the probability of more than $10d^3$ triangles is at most $1/60$. For $k=\lceil4M\log d/d\rceil$, the expected number of independent $k$-sets is at most \[ \binom Mk(1-d/M)^{\binom k2} \le\exp\{k\log(eM/k)-dk(k-1)/(2M)\}=o(1) \] as $M\to\infty$ with $d$ fixed and sufficiently large: the exponent is at most $-\tfrac12k\log d$ for large $M$. Consequently all three desired events occur simultaneously with positive probability. Delete the high-degree vertices and one vertex from each remaining triangle. For $M$ sufficiently large, the surviving graph has $m\ge0.8M$ vertices, maximum degree at most $2d$, and independence number less than $k\le5M\log d/d\le\rho m$. Join its components in a chain by bridges, using a fixed representative of each component for its at most two incident bridges. This preserves triangle-freeness, increases maximum degree by at most two, and cannot increase independence number. This proves $1$.

2. Attach many leaves

Fix $0<\eta<1$ and choose an integer $s\ge4/\eta$. Attach exactly $s$ new leaves to every vertex of a core $H$ satisfying $1$. Call the resulting graph $G$, its core vertex set $C$, and its pendant vertex set $P$. Then \[ |C|=m,\quad |P|=sm,\quad n=(s+1)m. \] Consider any triangle-free supergraph $G'$ of $G$ on the same vertices with diameter at most four, formed by adding $t$ edges. We will show $t>(1-\eta)n$. The case $t\ge n$ already suffices, so assume $t<n$. Let the graph induced by $P$ in $G'$ have $k$ connected components. Call such a component untouched if no added edge joins any of its vertices to $C$, and let $r$ be the number of untouched components. The edges within $P$, all of which are new, number at least $sm-k$. Every other component has at least one new edge to $C$, giving at least $k-r$ further edges. Hence \[ t\ge sm-r=n-m-r. \tag{2} \]

3. Bound the number of untouched components

Let $K$ count ordered pairs $(a,b)\in C^2$ whose distance in $G'$ is at most two, including the pairs $(a,a)$. Crucially, their short paths may use pendant vertices. Initially the number of such pairs is at most $m(D+1)^2$. Every vertex of $G'$ has at most $\alpha(H)$ neighbours in $C$: those neighbours must form an independent set in $H$, since $G'$ is triangle-free. Expose the $t$ new edges one at a time. A new ordered core pair at distance at most two must use the newly exposed edge in a path of length one or two. For an edge $xy$, the possible length-two paths have a core endpoint at $x$ or $y$ and their other core endpoint among the core neighbours of the other end. Counting both orientations gives at most $4\alpha(H)$ pairs, and the edge itself adds at most two. Thus the convenient bound \[ K\le m(D+1)^2+6t(\alpha(H)+1) \le m(D+1)^2+6n(\rho m+1) \tag{3} \] holds.

For two distinct untouched components $A,B$, take a path of length at most four between a chosen vertex of $A$ and one of $B$. A path leaving a component of $G'[P]$ must enter the core. Because $A$ and $B$ are untouched, the first entry edge and last exit edge are original leaf-parent edges. Let their core endpoints be $a,b$. At least one edge occurs before $a$ and after $b$, so $a,b$ have distance at most two in $G'$. Also $A$ contains an original child of $a$, and $B$ an original child of $b$. For a diagonal pair $(A,A)$, choose any original parent $a$ of one of its vertices and use $(a,a)$. Assign one such ordered core pair to every ordered pair of untouched components. A fixed $(a,b)$ can be assigned at most $s^2$ times: there are at most $s$ pendant components containing a child of each of $a,b$. Therefore \[ r^2\le s^2K. \tag{4} \] Combining $3$--$4$, \[ \frac rn\le\frac{s}{s+1} \sqrt{\frac{(D+1)^2}{m}+6(s+1)\left(\rho+\frac1m\right)}. \tag{5} \] Choose $d$ large enough that $6(s+1)\rho<\eta^2/64$, and then choose the core order $m$ large enough that the remaining terms inside the square root total less than $\eta^2/64$. Formula $5$ gives $r/n<\eta/4$, while $m/n=1/(s+1)<\eta/4$. Formula $2$ now yields \[ \boxed{t>(1-\eta/2)n>(1-\eta)n.} \] The construction permits arbitrarily large $m$, so this disproves the existence of any fixed positive saving in the conjecture.

Verification and conclusion

The core is connected before leaves are attached. All intermediate subgraphs of $G'$ remain triangle-free, so the bound on core neighbours applies at every edge-exposure step. The argument counts distance two in the whole extension, which is necessary because a newly added pendant vertex path can shorten distances between core vertices. Finally, $d$ is fixed before $m$ tends to infinity; no uniform random-graph estimate in a growing $d$ is being assumed.

Status: solved in the negative. The displayed proof establishes the qualitative counterexample completely. Its source is the known pendant construction; no novelty or local Lean verification is claimed.

Sources

• https://www.erdosproblems.com/619 and https://www.erdosproblems.com/forum/thread/619, checked 24 September 2026; the discussion specifies the diameter-at-most-four convention and the counterexample mechanism.
• N. Kuhn, associated proof materials, https://github.com/nick-kuhn/erdos-619/.

Completion estimate: 100% for the qualitative disproof requested.

Problem 619 $\#619$

1) ROUND-2 OBJECTIVE

Path (C): the full conjecture remains open, so I will prove it for a genuinely new infinite family that was not covered in Round 1, namely all cycles, including the odd cycles. The target is a linear bound with a positive saving: \[ h_4(C_n)\le \left\lceil \frac n3\right\rceil -1. \]

This is a strict extension beyond the Round-1 bipartite result, since odd cycles are non-bipartite.

2) Round-1 FOUNDATION USED

I use one Round-1 result:

1. If $G$ is connected bipartite on $n$ vertices, then $h_4(G)\le n/2$.

This will only be used as context/comparison; the proof below is self-contained and addresses a new non-bipartite family.

3) NEW INSIGHT / TOOL (ROUND-2)

The new construction replaces the bipartite "join one side to a hub" idea by a sparse dominating set of portals on the cycle.

The portals form a dominating set $P$ of size about $n/3$, and one carefully chosen portal $c\in P$ is at cyclic distance at least $3$ from every other portal. Adding only the star edges from $c$ to $P\setminus\{c\}$ keeps the graph triangle-free, while the portal star has diameter $2$. Since every cycle vertex is within distance $1$ of a portal, the whole augmented graph has diameter at most $4$.

4) ATTACK PLAN (ROUND-2)

The exact Round-1 obstacle was this: a single radius-$2$ hub is hard to realize in non-bipartite triangle-free graphs because indiscriminate hub attachments create triangles.

For cycles, the plan overcomes that obstacle by using only a very sparse set of hub attachments.

1. Choose a dominating set $P$ on $C_n$ with $|P|=\lceil n/3\rceil$.
2. Choose a center $c\in P$ that is at cyclic distance at least $3$ from every other portal.
3. Add the star edges $cp$ for $p\in P\setminus\{c\}$.
4. Prove:
   • no triangle is created, because $c$ has no common cycle-neighbor with any other portal;
   • diameter is at most $4$, because every vertex is within distance $1$ of a portal and the portal graph has diameter $2$.

5) WORK (ROUND-2)

Theorem 5.1.

For every cycle $C_n$ with $n\ge 5$, \[ h_4(C_n)\le \max\left(0,\left\lceil \frac n3\right\rceil -1\right). \] In particular, for odd cycles, \[ h_4(C_n)\le \left\lceil \frac n3\right\rceil -1 < \left(1-\frac23\right)n \] for all sufficiently large $n$.

Proof.

If $n\le 9$, then \[ \operatorname{diam}(C_n)=\left\lfloor \frac n2\right\rfloor \le 4, \] so $h_4(C_n)=0$. Thus assume $n\ge 10$.

Label the cycle vertices by $0,1,\dots,n-1$ modulo $n$.

Case 1: $n=3q$. Let \[ P=\{0,3,6,\dots,3q-3\}, \qquad c=0. \] Then $|P|=q=\lceil n/3\rceil$.

Case 2: $n=3q+1$. Let \[ P=\{0,3,6,\dots,3q-3,\,3q-1\}, \qquad c=3. \] Then $|P|=q+1=\lceil n/3\rceil$.

Case 3: $n=3q+2$. Let \[ P=\{0,3,6,\dots,3q\}, \qquad c=3. \] Then $|P|=q+1=\lceil n/3\rceil$.

In every case, define $H$ by adding the star edges \[ cp \qquad (p\in P\setminus\{c\}) \] to the cycle.

We now verify the three required properties.

(i) $P$ is a dominating set of $C_n$.

This is immediate from the construction: along the cycle, the consecutive gaps between portals have length at most $3$, so every cycle vertex lies either in $P$ or next to a portal. Equivalently, every vertex of $C_n$ is at distance at most $1$ from some portal.

(ii) $H$ is triangle-free.

On a cycle, two vertices have a common neighbor if and only if they are at cyclic distance $2$.

So it is enough to check that the center $c$ is at cyclic distance at least $3$ from every other portal. This is straightforward from the case definitions:

• if $n=3q$, then the other portals are at distances $3,6,\dots,3q-3$ from $0$, and the wrap-around distance to the last portal is $3$;
• if $n=3q+1$, then $c=3$ and the other portals are $0,6,9,\dots,3q-3,3q-1$; their cyclic distances from $3$ are at least $3$;
• if $n=3q+2$, then $c=3$ and the other portals are $0,6,9,\dots,3q$; again their cyclic distances from $3$ are at least $3$.

Hence no added edge $cp$ can complete a triangle with cycle edges.

Also, because the portals are pairwise nonadjacent on the cycle, no triangle can use two added edges $cp$ and $cq$. Therefore $H$ is triangle-free.

(iii) $\operatorname{diam}(H)\le 4$.

Take any two vertices $u,v$ of the cycle. By (i), choose portals $p(u),p(v)\in P$ such that \[ \operatorname{dist}_H(u,p(u))\le 1, \qquad \operatorname{dist}_H(v,p(v))\le 1. \] Inside the portal set $P$, the added edges form a star centered at $c$, so any two portals are at distance at most $2$ in $H$. Therefore \[ \operatorname{dist}_H(u,v) \le \operatorname{dist}_H(u,p(u)) + \operatorname{dist}_H(p(u),p(v)) + \operatorname{dist}_H(p(v),v) \le 1+2+1=4. \] Thus $\operatorname{diam}(H)\le 4$.

Finally, the number of added edges is exactly \[ |P|-1=\left\lceil \frac n3\right\rceil -1. \] This proves the theorem. $\square$

Corollary 5.2.

The original Erdős--Gyárfás--Ruszinkó question has a positive answer for the infinite family of cycles. Indeed one may take $c=2/3$ for this family.

6) ADVERSARIAL VERIFICATION

1. The small cycles $C_5,C_6,C_7,C_8,C_9$ were separated out at the start, since they already have diameter at most $4$.
2. The only possible way to create a triangle in the construction is via one added edge and two cycle edges, or two added edges and one cycle edge. Both were checked explicitly.
3. The diameter proof uses only two facts:
   • every vertex is within distance $1$ of a portal;
   • the portal graph is a star, hence has diameter $2$.
   No hidden assumptions about parity are used.
4. The edge count is exact for the construction: \[ |F|=|P|-1=\left\lceil \frac n3\right\rceil -1. \]

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

A new non-bipartite infinite family is now settled:

\[ h_4(C_n)\le \max\left(0,\left\lceil \frac n3\right\rceil -1\right) \qquad\text{for every cycle } C_n. \]

In particular, the conjectured linear saving holds for all odd cycles with a much stronger constant than Round 1 provided: \[ h_4(C_n)\le \left\lceil \frac n3\right\rceil -1. \]

The full problem for arbitrary connected triangle-free graphs remains open.

8) COMPLETION ESTIMATE

COMPLETION: 56%

9) REFERENCES

• T. F. Bloom, Erdős Problem #619, accessed 2026-03-08.
• Round-1 notes from the previous iteration of this investigation (used only for the bipartite comparison bound listed in Section 2).

Problem 619

FORMAL RESTATEMENT

Let $G=(V,E)$ be a finite simple graph. For an integer $r\ge 2$, define $h_r(G)$ as follows (for triangle-free $G$): \[ h_r(G)\ :=\ \min\left\{|F|:\ F\subseteq \binom{V}{2}\setminus E,\ \text{$G+F$ is triangle-free and has diameter at most $r$}\right\}. \] (Here $G+F$ denotes the graph on the same vertex set with edge set $E\cup F$.)

The question in the prompt (Erdős--Gyárfás--Ruszinkó, 1998) asks whether there exists an absolute constant $c>0$ such that \[ \forall\ \text{connected triangle-free graphs $G$ on $n$ vertices},\qquad h_4(G)\ <\ (1-c)n. \]

QUICK LITERATURE/CONTEXT CHECK

Erdős--Gyárfás--Ruszinkó $1998$ prove that for every connected triangle-free $n$-vertex graph, \[ h_3(G)\le n-1, \] and they also prove that \[ h_5(G)\le \frac{n-1}{2}. \] They explicitly pose the diameter-$4$ question as an open problem (their Problem 4.3): whether the $n-1$ bound can be improved by a positive fraction. They remark that without the triangle-free restriction, diameter-$4$ can be achieved by adding at most $n/2$ edges (and this is best possible), referring to work of Chung and Garey.

ATTACK PLAN

The goal is to force diameter $\le 4$ while avoiding creation of triangles. A natural sufficient condition is to make the augmented graph have radius $\le 2$: if there is a vertex $x$ at distance at most 2 from every vertex, then diameter is at most 4. However, in a triangle-free graph we may only add an edge $uv$ if $u$ and $v$ have no common neighbor (otherwise we would create a triangle).

Approaches:

1. Prove the statement for special classes, e.g. bipartite graphs (where any added edge across a bipartition preserves triangle-freeness).
2. Try to extend the matching-based construction of Erdős--Gyárfás--Ruszinkó that gives diameter $\le 4$ with $n-\nu(G)$ added edges (where $\nu(G)$ is matching number), and find a complementary construction using $O(\nu(G))$ edges that also yields diameter $\le 4$.
3. Explore whether odd cycles force an obstruction (since triangle-free graphs may have large chromatic number). Possibly reduce to controlling a large bipartite "core" plus a small exceptional set.

WORK

A complete positive result for connected bipartite graphs.

Let $G=(V,E)$ be connected and bipartite with bipartition $V=A\sqcup B$. Assume without loss that $|A|\le |B|$. Pick any vertex $a\in A$. Let \[ F\ :=\ \{\{a,b\}:\ b\in B\ \text{and}\ \{a,b\}\notin E\}. \] That is, we add all missing edges from $a$ to the opposite side $B$.

Implication.

For connected bipartite graphs, the desired inequality holds with $c=1/2$: \[ \boxed{\text{If $G$ is connected bipartite on $n$ vertices, then } h_4(G)\le \frac{n}{2}.} \]

Why this does not settle the triangle-free case.

If $G$ is triangle-free but non-bipartite, adding edges can easily create triangles due to existing odd-cycle structure: an added edge $uv$ is forbidden whenever $u$ and $v$ share a neighbor. The bipartite "join one side to a hub" construction above relies crucially on the existence of a bipartition, which fails in general.

Connection to the matching-based construction in EGR (sketch only).

Erdős--Gyárfás--Ruszinkó show (among other things) that if $\nu(G)=t$ is the matching number, then one can build a triangle-free supergraph of diameter at most $4$ by adding at most $n-t$ edges. This is useful when $t$ is a positive fraction of $n$, but it does not yield a uniform $c>0$ because $t$ can be small (e.g. a star has $t=1$) while already having small diameter. The missing ingredient is a complementary "$O(t)$-edge" diameter-$4$ augmentation to combine with $n-t$.

VERIFICATION

• In the bipartite construction, triangle-freeness is immediate because bipartite graphs have no odd cycles, in particular no 3-cycles.
• The diameter bound is a direct radius-$2$ argument.
• Edge count is deterministic and worst-case sharp up to constants (balanced complete bipartite graphs already have diameter $2$ so need $0$ edges; paths show that $\Theta(n)$ edges can be needed in some sparse bipartite cases, but the bound $n/2$ is uniform).

FINAL

UNRESOLVED

1. Where and why the attempt fails. The obstacle is extending the clean bipartite "make a radius-2 hub" augmentation to all triangle-free graphs. In non-bipartite triangle-free graphs, adding many edges incident to a hub vertex typically creates triangles because endpoints may have common neighbors. I did not find a uniform way to add $<(1-c)n$ edges (with fixed $c>0$) that guarantees diameter $\le 4$ while maintaining triangle-freeness.

2. Strongest partial result proved here. If $G$ is connected and bipartite on $n$ vertices, then $h_4(G)\le n/2$ by an explicit construction (add all missing edges from a vertex in the smaller side to the opposite side).

3. Most plausible next ideas. Try to adapt the Erdős--Gyárfás--Ruszinkó matching-based approach: find an augmentation with $O(\nu(G))$ edges that achieves diameter $\le 4$ (not $\le 5$), and then combine with their $n-\nu(G)$ augmentation to obtain a uniform fraction improvement. Alternatively, attempt a decomposition of an arbitrary triangle-free graph into a large bipartite subgraph plus a controlled exceptional set, and run the bipartite augmentation on the large part while carefully connecting the exceptional vertices without creating triangles.

4. Small cases / computations. No exhaustive search was performed. The bipartite lemma can be checked on small examples (paths, even cycles) by hand; it gives the correct qualitative behavior (diameter becomes $\le 4$ after adding $O(n)$ edges). Determining the true worst-case behavior of $h_4(G)$ over all triangle-free $G$ appears to require ideas beyond this basic augmentation.

COMPLETION ESTIMATE

COMPLETION ESTIMATE: 30%.