we-solve (beta)

Math-5773-A2 · revision r1 · on Math-5773

gpt pro 5.2 attempt on Math-5773

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: solved. Claims here do not change the source status.

Manuscript

Contents
  1. Problem 619
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. ATTACK PLAN
  5. WORK
  6. A complete positive result for connected bipartite graphs.
  7. Implication.
  8. Why this does not settle the triangle-free case.
  9. Connection to the matching-based construction in EGR (sketch only).
  10. VERIFICATION
  11. FINAL
  12. COMPLETION ESTIMATE

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$.
Claim: The augmented graph $H:=G+F$ is triangle-free and has diameter at most $4$.
Proof: Triangle-free: $H$ is still bipartite with the same bipartition $A\sqcup B$, since all added edges go from $a\in A$ to $B$. Any bipartite graph is triangle-free.

Diameter $\le 4$: We show that every vertex is within distance $\le 2$ of $a$ in $H$. If $v\in B$, then $av\in E(H)$ by construction, so $\mathrm{dist}_H(a,v)=1$. If $v\in A$, then since $G$ is connected, $v$ has a neighbor $b\in B$ in $G$ (hence also in $H$). Then $\mathrm{dist}_H(a,v)\le \mathrm{dist}_H(a,b)+\mathrm{dist}_H(b,v)=1+1=2$. Thus the eccentricity of $a$ in $H$ is at most $2$, and therefore the diameter of $H$ is at most $4$. ∎

Claim: The number of added edges satisfies $|F|\le |B|\le \tfrac{n}{2}$.
Proof: We add at most one edge from $a$ to each vertex of $B$, hence $|F|\le |B|$. Since $|A|\le |B|$ and $|A|+|B|=n$, we have $|B|\le n/2$. ∎
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%.