Erdős Problem #64

Problem 64: The Erdős--Gyárfás conjecture (power-of-two cycle lengths)

1) ROUND-4 OBJECTIVE

Path (A) --- proof, via a sharper minimal-counterexample reduction. Round 3 reduced any putative counterexample to a connected edge-minimal graph $H$ with $\delta(H)=3$ and $V_{\ge 4}(H)$ independent, and obtained the quantitative bound that at least $4/7$ of the vertices have degree exactly $3$. The most promising next step is to strengthen that reduction itself: show that edge-minimality forces interaction among the degree-$3$ vertices, not just a weak counting inequality. This succeeds. I prove that every degree-$3$ vertex of $H$ has a degree-$3$ neighbor, which upgrades the $4/7$ bound to a sharp $2/3$ bound and isolates the equality case.

2) Round-3 FOUNDATION USED

I use the following Round 3 results without reproving them:

• Round-3 Lemma 5.1 and Corollary 5.2. If a counterexample exists, then there is a connected edge-minimal counterexample $H$ such that $\delta(H)=3$, and the set \[ B:=V_{\ge 4}(H)=\{v\in V(H): d_H(v)\ge 4\} \] is independent.
• Round-3 Lemma 5.3. With \[ A:=V_3(H)=\{v\in V(H): d_H(v)=3\}, \] one has $|A|\ge 4|V(H)|/7$.
• Round-2/3 validated literature inputs. Any counterexample has diameter at least $3$; every $P_{13}$-free graph with minimum degree at least $3$ satisfies the conjecture; hence every counterexample contains an induced $P_{13}$; any counterexample has at least $17$ vertices; and any bipartite counterexample has at least $32$ vertices.

3) NEW INSIGHT / TOOL (ROUND-4)

The new tool is a subgraph-minimality upgrade of Round 3's edge-minimality. For the chosen edge-minimal counterexample $H$, no proper subgraph of $H$ can still have minimum degree at least $3$, because every proper subgraph has fewer edges and cannot create new cycles.

This stronger minimality has three consequences.

1. Every degree-$3$ vertex has a degree-$3$ neighbor.
2. The induced subgraph $H[A]$ has minimum degree at least $1$.
3. Consequently, \[ |A|\ge 2|B|, \] so at least $2/3$ of all vertices have degree exactly $3$.

Moreover, equality is rigid: if $|A|=2|B|$, then $H[A]$ is a perfect matching and every vertex of $B$ has degree exactly $4$.

4) ATTACK PLAN (ROUND-4)

After Round 3, the exact unresolved gap was that the edge-minimal core still allowed a substantial population of vertices of degree at least $4$; the bound $|A|\ge 4|V(H)|/7$ was too weak to make the counterexample class genuinely narrow.

The Round 4 plan is therefore:

• strengthen Round 3 Lemma 5.1 from single-edge deletions to arbitrary proper subgraphs;
• use that stronger minimality to prove that vertices of degree $3$ cannot be supported entirely by higher-degree neighbors;
• convert this local structural fact into a global counting theorem $|A|\ge 2|B|$;
• isolate the equality case as a sharply formulated obstruction.

This overcomes the main Round 3 obstacle by forcing the degree-$3$ vertices to form a nontrivial internal backbone.

5) WORK (ROUND-4)

Lemma 5.9 (new: subgraph-minimality of the edge-minimal counterexample).

Let $H$ be the connected edge-minimal counterexample provided by Round 3 Lemma 5.1. Then no proper subgraph $F\subsetneq H$ satisfies $\delta(F)\ge 3$.

Proof. Suppose that some proper subgraph $F\subsetneq H$ has $\delta(F)\ge 3$. Since $F$ is a proper subgraph, it has strictly fewer edges than $H$. Also, every cycle of $F$ is a cycle of $H$, because subgraphs do not create new cycles. Since $H$ has no cycle whose length is a power of $2$, neither does $F$. Therefore $F$ is also a counterexample, contradicting the choice of $H$ as a counterexample with the minimum possible number of edges. $\square$

Corollary 5.10 (new: every degree-$3$ vertex meets $A$).

Every vertex of $A$ has at least one neighbor in $A$. Equivalently, the induced subgraph $H[A]$ has minimum degree at least $1$.

Proof. Let $a\in A$. Suppose, for contradiction, that every neighbor of $a$ lies in $B$. Since $d_H(a)=3$, the graph $H-a$ is a proper subgraph of $H$. Every neighbor of $a$ had degree at least $4$ in $H$, so after deleting $a$ each of those neighbors still has degree at least $3$. All other vertex degrees are unchanged. Hence \[ \delta(H-a)\ge 3. \] This contradicts Lemma 5.9. Therefore $a$ has a neighbor in $A$. Since $a\in A$ was arbitrary, $\delta(H[A])\ge 1$. $\square$

Theorem 5.11 (new: the $2/3$ theorem for the edge-minimal core).

With $A=V_3(H)$ and $B=V_{\ge 4}(H)$ as above, \[ |A|\ge 2|B|. \] Equivalently, \[ |A|\ge \frac{2}{3}|V(H)|, \qquad |B|\le \frac{1}{3}|V(H)|. \] In particular, at least two-thirds of the vertices of $H$ have degree exactly $3$.

Proof. By Corollary 5.10, every vertex of $H[A]$ has degree at least $1$ inside $H[A]$. Hence \[ 2e_H(A)\ge |A|. \] Every vertex of $A$ has total degree $3$, so \[ 3|A| = 2e_H(A)+e_H(A,B). \] Using $2e_H(A)\ge |A|$, we obtain \[ e_H(A,B) = 3|A|-2e_H(A) \le 2|A|. \] On the other hand, Round 3 Corollary 5.2 says that $B$ is independent. Therefore every edge incident with a vertex of $B$ lies in $E_H(A,B)$, and since each vertex of $B$ has degree at least $4$, \[ e_H(A,B)=\sum_{b\in B} d_H(b)\ge 4|B|. \] Combining the two inequalities yields \[ 4|B|\le e_H(A,B)\le 2|A|, \] so $|A|\ge 2|B|$. Since $|V(H)|=|A|+|B|$, this is equivalent to \[ |A|\ge \frac{2}{3}|V(H)|, \qquad |B|\le \frac{1}{3}|V(H)|. \] $\square$

Corollary 5.12 (new: rigidity of the equality case).

Equality $|A|=2|B|$ in Theorem 5.11 holds if and only if both of the following are true:

1. every vertex of $B$ has degree exactly $4$;
2. the graph $H[A]$ is $1$-regular, i.e. $H[A]$ is a disjoint union of edges (a perfect matching on $A$).

Proof. If $|A|=2|B|$, then the proof of Theorem 5.11 gives \[ 4|B|\le e_H(A,B)\le 2|A|=4|B|, \] so equality holds throughout. Hence \[ e_H(A,B)=4|B|, \] which forces $d_H(b)=4$ for every $b\in B$, because each $b\in B$ has degree at least $4$ and \[ e_H(A,B)=\sum_{b\in B} d_H(b). \] Also, \[ e_H(A,B)=2|A|. \] Substituting into \[ 3|A|=2e_H(A)+e_H(A,B) \] shows that \[ 2e_H(A)=|A|. \] Since Corollary 5.10 says that every vertex of $H[A]$ has degree at least $1$, the equality $2e_H(A)=|A|$ implies that every vertex of $H[A]$ has degree exactly $1$. Thus $H[A]$ is $1$-regular, hence a perfect matching.

Conversely, if every vertex of $B$ has degree $4$ and $H[A]$ is a perfect matching, then \[ 2e_H(A)=|A|, \qquad e_H(A,B)=3|A|-2e_H(A)=2|A|, \] while also \[ e_H(A,B)=\sum_{b\in B} d_H(b)=4|B|. \] Therefore $2|A|=4|B|$, i.e. \[ |A|=2|B|. \] $\square$

Lemma 5.13 (new: no component of $H[A]$ is closed under $B$-neighbors).

Assume $H[A]$ has at least two connected components. Then for every connected component $C$ of $H[A]$, there exists a vertex $b\in B$ that has a neighbor in $C$ and a neighbor in $A\setminus V(C)$.

Proof. Fix a connected component $C$ of $H[A]$, and let \[ S:=V(C)\cup \left(N_H(V(C))\cap B\right). \] Because $C$ is a connected component of $H[A]$, every neighbor in $A$ of a vertex of $C$ also lies in $C$. Thus every vertex of $C$ has all three of its neighbors inside $S$, so it has degree $3$ in $H[S]$.

Suppose, toward a contradiction, that every $b\in B\cap S$ has all its neighbors in $C$. Then each such $b$ keeps all of its neighbors in $H[S]$, and therefore has degree at least $4$ in $H[S]$. Hence \[ \delta(H[S])\ge 3. \] Since $H[A]$ has at least two connected components, there is a vertex of $A\setminus V(C)$, so $S\neq V(H)$. Therefore $H[S]$ is a proper induced subgraph of $H$, contradicting Lemma 5.9.

Thus some $b\in B\cap S$ must have a neighbor outside $C$. Since $B$ is independent, that outside neighbor must lie in $A\setminus V(C)$. $\square$

Updated obstruction profile after Round 4.

Combining the new Round 4 results with the validated inputs from Rounds 2 and 3, we obtain the following.

If a counterexample exists, then there is a connected edge-minimal counterexample $H$ such that:

1. $\delta(H)=3$;
2. $B=V_{\ge 4}(H)$ is independent;
3. every vertex of $A=V_3(H)$ has a neighbor in $A$;
4. at least $2/3$ of the vertices of $H$ lie in $A$;
5. if equality $|A|=2|B|$ holds, then $H[A]$ is a perfect matching and every vertex of $B$ has degree exactly $4$;
6. if $H[A]$ is disconnected, then every component of $H[A]$ is linked to another component through some vertex of $B$;
7. $\operatorname{diam}(H)\ge 3$;
8. $H$ contains an induced $P_{13}$;
9. $|V(H)|\ge 17$;
10. if $H$ is bipartite, then $|V(H)|\ge 32$.

Thus the unresolved core is now narrower than in Round 3: a putative counterexample must be degree-$3$-dominated by a full two-thirds margin, with the degree-$3$ vertices themselves forming a nontrivial internal scaffold.

6) ADVERSARIAL VERIFICATION

• Does Lemma 5.9 really strengthen Round 3 Lemma 5.1? Yes. Round 3 handled deletion of a single edge whose endpoints both had degree at least $4$. Lemma 5.9 applies to every proper subgraph. The key monotonicity fact is valid: passing to a subgraph never creates a new cycle.

• Could $H-a$ in Corollary 5.10 be disconnected, invalidating the contradiction? No. Connectivity is irrelevant for the contradiction. A disconnected graph with minimum degree at least $3$ and no power-of-two cycle is still a counterexample, since each component has minimum degree at least $3$ and every cycle of every component is also a cycle of the whole graph.

• Is the $2/3$ inequality sharp? The proof shows exactly where equality can occur: simultaneously $e_H(A,B)=2|A|=4|B|$ and $2e_H(A)=|A|$. Corollary 5.12 verifies that this is equivalent to the rigid configuration "all vertices of $B$ have degree $4$ and $H[A]$ is a perfect matching." No hidden assumptions are used.

• Is Lemma 5.13 stronger than mere connectivity of $H$? Yes. Connectivity only guarantees that each component of $H[A]$ has some neighbor in $B$. Lemma 5.13 proves that no component of $H[A]$ can be sealed off by $B$-vertices that connect only to that component; otherwise one gets a proper induced subgraph with minimum degree at least $3$.

• Interaction with Round 3. Theorem 5.11 strictly strengthens Round 3 Lemma 5.3: the lower bound on degree-$3$ vertices improves from $4|V(H)|/7$ to $2|V(H)|/3$. The earlier bound remains true but is now superseded.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED). The full Erdős--Gyárfás conjecture remains open in general, but Round 4 makes a genuine structural advance beyond Round 3:

• it upgrades edge-minimality to full subgraph-minimality (Lemma 5.9);
• it proves that every degree-$3$ vertex has a degree-$3$ neighbor (Corollary 5.10);
• it strengthens the Round 3 bound from $4/7$ to $2/3$ on the proportion of degree-$3$ vertices (Theorem 5.11);
• it characterizes the equality case $|A|=2|B|$ (Corollary 5.12);
• it proves that no connected component of $H[A]$ can be closed under all incident $B$-neighbors unless $H[A]$ itself is connected (Lemma 5.13).

The sharpest obstruction now isolated is this: any minimal counterexample must be a connected graph of diameter at least $3$, containing an induced $P_{13}$, in which at least two-thirds of all vertices have degree exactly $3$, every such vertex has another degree-$3$ neighbor, and the extremal equality case forces the degree-$3$ vertices to form a perfect matching while all remaining vertices have degree exactly $4$.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 68%.

9) REFERENCES

References

• [Erdos1997] P. Erdős, Some old and new problems in various branches of combinatorics, Discrete Mathematics 165--166 $1997$, 227--231.
• [Carr2025] A. Carr, Cycles of length 4 or 8 in graphs with diameter 2 and minimum degree at least 3, arXiv:2508.19302, 2025.
• [HegdeSandeepShashank2025] A. S. Hegde, R. B. Sandeep, and P. Shashank, Erdős--Gyárfás conjecture on graphs without long induced paths, arXiv:2410.22842v2, 2025.
• [HuShen2024] Z. Hu and C. Shen, The Erdős--Gyárfás conjecture holds for $P_{10}$-free graphs, Discrete Mathematics 347 $2024$, 114175.
• [NowEtAl2014] P. Salehi Nowbandegani, H. Esfandiari, M. H. Shirdareh Haghighi, and K. Bibak, On the Erdős--Gyárfás conjecture in claw-free graphs, Discussiones Mathematicae Graph Theory 34 $2014$, 635--640.

Erdős Problem #64: independent continuation

Date: 23 September 2026. Source versions read in full: 64.tex in gpt_pro_5.4.

1) OBJECTIVE AND MINIMALITY CONVENTION

Choose a counterexample with the fewest edges among all finite graphs of minimum degree at least three having no power-of-two cycle. This global choice is necessary; mere inability to delete one edge is weaker. Then no proper nonempty subgraph has minimum degree three. As in the source, $A=V_3(H)$, $B=V_{\ge4}(H)$, $B$ is independent, $\delta(H[A])\ge1$, and $|A|\ge2|B|$.

2) A STRONGER COMPONENT-DELETION CONDITION

Let $C$ be a component of $H[A]$ such that $H-C$ is nonempty. Every remaining vertex in $A$ keeps all its neighbours in $A$ and has no neighbour in $C$. Hence it retains degree three. If every $b\in B$ lost at most $d_H(b)-3$ neighbours, then $H-C$ would have minimum degree at least three, a contradiction. Therefore some $b\in B$ satisfies \[ |N_H(b)\cap C|\ge d_H(b)-2. \tag{1} \] This is stronger than requiring a component merely to share a neighbouring high-degree vertex with another component.

3) RIGIDITY OF THE TWO-THIRDS EQUALITY CASE

If $|A|=2|B|$, the source's counting proof forces $H[A]$ to be a perfect matching and every $b\in B$ to have degree four. Apply $1$ to a matching edge $aa'$. Its endpoints must share a neighbour $b\in B$. They cannot share two neighbours, since those four vertices would form a four-cycle. Therefore every matching edge has exactly one common neighbour in $B$. Each endpoint has two neighbours in $B$, so its neighbourhood takes the form \[ N(a)=\{a',b,x\},\qquad N(a')=\{a,b,y\}, \] where $b,x,y$ are distinct. In particular every matched pair belongs to a forced triangle. A vertex of $B$ can be the common centre of at most two such triangles, since each consumes two of its four incident edges. There are $|A|/2=|B|$ matched pairs, so the average number of these centred triangles per vertex of $B$ is one.

4) REMAINING OBSTRUCTION

These triangles are permitted: the forbidden lengths begin at four. Contracting a matched edge or its triangle changes cycle lengths and can turn an allowed length into a power of two, so this structure cannot simply be suppressed while preserving the problem. I have not excluded the equality case or forced a longer forbidden cycle.

7) FINAL

UNRESOLVED. The minimal-counterexample profile is strengthened by $1$ and an exact forced-triangle description, without claiming the conjecture is proved. Original statement checked: https://www.erdosproblems.com/64.

8) COMPLETION ESTIMATE

COMPLETION: 12% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Problem 64: The Erdős--Gyárfás conjecture (power-of-two cycle lengths)

1) ROUND-2 OBJECTIVE

Path (A) --- proof. The Round-1 output produced (i) an even cycle and (ii) a short-cycle bound, but did not force a cycle of length $2^k$. In Round 2 I push the "structural restriction" approach: prove the conjecture for additional nontrivial subclasses (notably diameter $2$ graphs) and derive new necessary conditions for any putative counterexample.

2) ROUND-1 FOUNDATION USED

I rely on the following Round-1 facts exactly as stated in 64.tex:

• Round-1 Lemma 1. Every finite graph with minimum degree at least $3$ contains an even cycle.
• Round-1 Lemma 2. If $|V(G)|=n$ and $\delta(G)\ge 3$, then $G$ contains a cycle of length at most $2\log_2 n + 3$.
• Round-1 computation. The conjecture holds for all graphs on $n\le 7$ vertices.

Note. The Round-1 remark "a minimal counterexample must have girth at least $5$" is too strong: a counterexample may contain triangles (length $3$ is not a power of $2$). The correct immediate necessary condition is only "no $4$-cycle" (and no $8$-, $16$-, …). I do not use the incorrect girth claim.

3) NEW INSIGHT / TOOL (ROUND-2)

1. A new local construction (Lemma lem:diam2-notriangle-edge) giving an explicit $8$-cycle in any diameter-$2$, $C_4$-free graph that has an edge not contained in any triangle. This is a streamlined "Case 2" argument.
2. A published diameter-$2$ verification: every graph of diameter $2$ and minimum degree at least $3$ has a $4$-cycle or an $8$-cycle (Carr, 2025) [Carr2025].
3. Sharper computer-aided bounds and $P_k$-free confirmations (Hegde--Sandeep--Shashank, 2025):
   • extensive searches show a counterexample needs at least $17$ vertices, a cubic counterexample at least $30$ vertices, and a bipartite counterexample at least $30$ vertices [HegdeSandeepShashank2025, pp. 1--2];
   • the conjecture is proved for all $P_{13}$-free graphs, and a stronger "$4$- or $8$-cycle" statement for $P_{12}$-free graphs [HegdeSandeepShashank2025, Theorems 1--2].

4) ATTACK PLAN (ROUND-2)

Gap after Round 1. We know an even cycle exists and some cycle is short, but the set of powers of $2$ is sparse; Round 1 had no mechanism to target the exact lengths $4,8,16,\dots$.

Round 2 plan. Use structural constraints to force small powers of $2$:

• Prove the conjecture for the subclass of diameter-$2$ graphs (done via Carr's theorem, plus a simplified subcase proof here).
• Deduce that any minimal counterexample must have diameter at least $3$.
• Incorporate known computer-aided lower bounds and additional verified classes to shrink the plausible search space of counterexamples.

5) WORK (ROUND-2)

Lemma 3 (new: a diameter-$2$ "edge not in a triangle" forces an $8$-cycle).

Let $G$ be a finite simple graph with $\operatorname{diam}(G)=2$ and $\delta(G)\ge 3$. Assume $G$ has no $4$-cycle and contains an edge $uv$ such that $u$ and $v$ have no common neighbor (equivalently, the edge $uv$ is not contained in any triangle). Then $G$ contains an $8$-cycle.

Proof. Because $\delta(G)\ge 3$, pick two distinct neighbors $u_1,u_2\in N(u)\setminus\{v\}$ and two distinct neighbors $v_1,v_2\in N(v)\setminus\{u\}$.

Step 1: no cross-adjacencies. If some $u_i$ were adjacent to some $v_j$, then \[ u\,u_i\,v_j\,v\,u \] would be a $4$-cycle, contradicting the assumption. Hence \begin{equation} \label{wsref-0-65-71-3a-6e-6f-63-72-6f-73-73} u_i\not\sim v_j\qquad\text{for all }i\in\{1,2\},\ j\in\{1,2\}. \end{equation} In particular, $u_1\neq v_1$ and $u_2\neq v_2$.

Step 2: pick two distance-$2$ connectors. Since $\operatorname{diam}(G)=2$, we have $\operatorname{dist}(u_1,v_1)\le 2$. By (eq:nocross) it is not $1$, so it is $2$; choose a vertex $x$ adjacent to both $u_1$ and $v_1$. Similarly, $\operatorname{dist}(u_2,v_2)=2$; choose a vertex $y$ adjacent to both $u_2$ and $v_2$.

Step 3: distinctness checks (to ensure a simple $8$-cycle). We claim the vertices \[ u,\ u_1,\ x,\ v_1,\ v,\ v_2,\ y,\ u_2 \] are pairwise distinct.

• $x\neq u$: otherwise $u\sim v_1$, making $v_1$ a common neighbor of $u$ and $v$, contradicting the hypothesis on $uv$.
• $x\neq v$: otherwise $v\sim u_1$, again giving a $4$-cycle $u\,u_1\,v\,u$ (since $u\sim v$), or equivalently contradicting (eq:nocross).
• $x\notin\{u_1,v_1\}$ since $x$ is adjacent to both $u_1$ and $v_1$ while $u_1\not\sim v_1$.
• Likewise $y\notin\{u,v,u_2,v_2\}$.
• $x\neq y$: if $x=y$, then $u\,u_1\,x\,u_2\,u$ is a $4$-cycle (using $u\sim u_1$, $u\sim u_2$ and $x\sim u_1,u_2$).

Also $u_1\neq u_2$ and $v_1\neq v_2$ by construction.

Step 4: the $8$-cycle. All edges in the cyclic sequence \[ u\! -\! u_1\! -\! x\! -\! v_1\! -\! v\! -\! v_2\! -\! y\! -\! u_2\! -\! u \] exist by construction, and by Step 3 the vertices are distinct; hence this is a simple cycle of length $8$. $\square$

Theorem 4 (diameter $2$ case: $4$- or $8$-cycle).

Avery Carr proved:

If $\operatorname{diam}(G)=2$ and $\delta(G)\ge 3$, then $G$ contains a cycle of length $4$ or $8$.

[Carr2025]. (Carr's proof splits into whether a chosen edge lies in a triangle; Lemma lem:diam2-notriangle-edge gives a short proof of the "no triangle on the edge" subcase under the additional assumption "no $4$-cycle", while Carr's theorem handles both subcases without assuming $C_4$-freeness.)

Corollary 5 (new restriction on counterexamples).

Any counterexample to the Erdős--Gyárfás conjecture with $\delta(G)\ge 3$ must satisfy $\operatorname{diam}(G)\ge 3$.

Proof. If $\operatorname{diam}(G)=2$, then by Theorem 4 the graph contains a $4$-cycle or an $8$-cycle, i.e., a cycle of length $2^k$ with $k\in\{2,3\}$, contradicting that it is a counterexample. $\square$

Known computer-aided lower bounds (beyond Round 1).

Hegde--Sandeep--Shashank report that extensive searches show:

• any counterexample has at least $17$ vertices;
• any cubic counterexample has at least $30$ vertices;
• any bipartite counterexample has at least $30$ vertices,

see [HegdeSandeepShashank2025, p. 2].

Known $P_k$-free confirmations (beyond Round 1).

Hegde--Sandeep--Shashank prove the conjecture for all $P_{13}$-free graphs [HegdeSandeepShashank2025, Theorem 1], and in fact show that every $P_{12}$-free graph with $\delta\ge 3$ contains a $4$-cycle or an $8$-cycle [HegdeSandeepShashank2025, Theorem 2].

6) ADVERSARIAL VERIFICATION

• Lemma lem:diam2-notriangle-edge: quantifiers and edge-cases. The construction requires only $\delta\ge 3$ to choose $u_1,u_2$ and $v_1,v_2$. It also uses only the hypotheses "$\operatorname{diam}=2$", "no $4$-cycle", and "$uv$ not in any triangle". The only delicate point is ensuring the cycle is simple. The distinctness checks explicitly rule out identifications such as $x=u$ (which would force $u\sim v_1$ and create a common neighbor of $u$ and $v$) and $x=y$ (which would create a $4$-cycle $u u_1 x u_2 u$). Thus the produced $8$-cycle is genuine.

• Correction of the Round-1 "girth" remark. A counterexample need not be triangle-free; only $4,8,16,\dots$ are forbidden. Hence "girth at least $5$" does not follow. None of the Round-1 lemmas depend on that remark, and Round 2 avoids using it.

• External results usage. Theorem 4 is imported from [Carr2025]; Corollary 5 uses it only via its statement and matches the hypotheses. The numerical lower bounds and $P_k$-free theorems are taken from [HegdeSandeepShashank2025].

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED). The full Erdős--Gyárfás conjecture remains open in general. Round 2 adds:

• a clean $8$-cycle construction in the diameter-$2$, $C_4$-free, "edge not in a triangle" regime (Lemma lem:diam2-notriangle-edge);
• a diameter-based exclusion: any counterexample must have diameter at least $3$ (Corollary 5), using Carr's theorem;
• stronger verified classes and search bounds from the recent literature (counterexample size $\ge 17$, and $P_{13}$-free verified).

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 45%.

9) REFERENCES

References

• [Erdos1997] P. Erdős, Some old and new problems in various branches of combinatorics, Discrete Mathematics 165--166 $1997$, 227--231.
• [LiMo20] X. Liu and R. Montgomery, A solution to Erdős and Gyárfás's conjecture for graphs of large average degree, Journal of Combinatorial Theory, Series B 142 $2020$, 186--208.
• [HegdeSandeepShashank2025] A. S. Hegde, R. B. Sandeep, and P. Shashank, Erdős--Gyárfás conjecture on graphs without long induced paths, arXiv:2410.22842v2 $2025$.
• [Carr2025] A. Carr, Cycles of length 4 or 8 in graphs with diameter 2 and minimum degree at least 3, arXiv:2508.19302 $2025$.