Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle

Statement

Does every finite graph with minimum degree at least 3 contain a cycle of length $2^k$ for some $k \geq 2$ (i.e. a cycle of length 4, 8, 16, 32, ...)?

This is the Erdős–Gyárfás conjecture (erdosproblems.com/64, verified by direct fetch). Erdős and Gyárfás in fact conjectured the answer is negative, and moreover conjectured a *strengthening*: for every $r$ there is a graph of minimum degree at least $r$ with no power-of-2 cycle at all — i.e. that no finite minimum-degree threshold ever forces one. That stronger conjecture is now known to be false (see Literature state); problem #64 itself, restricted to the tight case minimum-degree-exactly-$\geq 3$, remains open.

Facts

- Prize $1000; status open, falsifiability finite-counterexample (erdosproblems.com/64, directly fetched, reflects site-owner T.F. Bloom's belief). - Falsifiable: yes — a single finite graph with min degree $\geq 3$ and no cycle of length $4, 8, 16, 32,\dots$ disproves it. Purely combinatorial, machine-checkable. - Origin: [Er93,p.343], [Er94b], [Er95,p.174], [Er96], [Er97b], [Er97c] — Erdős restated it repeatedly through the 1990s; jointly conjectured with Gyárfás. Listed as #69 in the "Extremal Graph Theory" graphs problem collection (erdosproblems.com/64). - The strengthened Erdős–Gyárfás conjecture is disproved: Hong Liu and Richard Montgomery, "A solution to Erdős and Hajnal's odd cycle problem," arXiv:2010.15802 (2020), published *J. Amer. Math. Soc.* 36 (2023) — this is the "[LiMo20]" cited throughout erdosproblems.com. Its Theorem 1.1 shows: if the *average* degree of $G$ is sufficiently large (above some absolute constant), then there is some $\ell$ such that $G$ contains a cycle of every even length in $[(\log \ell)^8, \ell]$ — in particular a power-of-2 cycle. Since average degree $\geq$ minimum degree, this settles problem #64 affirmatively once the minimum-degree threshold is large enough, and directly falsifies the Erdős–Gyárfás belief that arbitrarily-high minimum degree could still avoid power-of-2 cycles forever (erdosproblems.com/64, erdosproblems.com/63). The paper's abstract (arxiv.org/abs/2010.15802) frames this as a byproduct of solving the unrelated Erdős–Hajnal odd-cycle-reciprocal-sum problem, using one unified method that also confirms a 1984 Thomassen conjecture on complete-graph subdivisions. - **This same paper resolves Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often (PROVED): "does every graph with infinite chromatic number contain a cycle of length $2^n$ for infinitely many $n$?" — via de Bruijn–Erdős + Theorem 1.1 of [LiMo20] (erdosproblems.com/63, which explicitly cross-links "See also [64]"). - This same paper gives the sharp asymptotic bound for Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) (still open on its second half): for the Erdős–Hajnal sum-of-reciprocals-of-cycle-lengths problem, [LiMo20] proves $\sum 1/a_i \geq (\tfrac12 - o(1))\log k$, asymptotically optimal (erdosproblems.com/65). - Confirmed for restricted graph classes (per Alfaiz's comment on erdosproblems.com/forum/discuss/64, 06 Dec 2025, listing refs to the primary papers): (i) $K_{1,m}$-free graphs, min degree $\geq m{+}1$ or max degree $\geq 2m{-}1$ — Shauger [Sh98], Congr. Numer. 134 (1998) 61-65. (ii) Planar claw-free graphs — Daniel & Shauger [DaSh01], Congr. Numer. 153 (2001) 129-139. (iii) 3-connected cubic planar graphs — Heckman & Krakovski [HeKr13], Electron. J. Combin. 20(2) (2013) #P7. (iv) Cayley graphs on generalized quaternion, dihedral, semidihedral groups and groups of order $p^3$ — Ghaffari & Mostaghim [GhMo18]. (v) Cayley graphs of order $2p^2$ and $4p$ — Ghasemi & Varmazyar [GhVa21]. (vi) $P_8$-free graphs — Gao & Shan [GaSh22], confirmed independently at arxiv.org/abs/2109.01277 (shows a cycle of length 4 or 8 specifically). (vii) $P_{10}$-free graphs — Hu & Shen [HuSh24], confirmed independently at arxiv.org/abs/2308.05675 (also length 4 or 8). (viii) Diameter-2 graphs — A. Carr [Ca26], arxiv.org/abs/2508.19302 ("Cycles of Length 4 or 8 in Graphs with Diameter 2 and Minimum Degree at Least 3", submitted 25 Aug 2025). (ix) $P_{13}$-free graphs (general power-of-2 statement) and $P_{12}$-free graphs (specific 4-or-8 statement) — Hegde, Sandeep & Shashank, arXiv:2410.22842 (v2, 11 Feb 2025), github.com/rbsandeep/Erdos-Gyarfas. This paper is currently absent from erdosproblems.com's own literature list (verified 2026-07-03: neither the main page nor the Alfaiz Dec-2025 comment cites it) — a real gap in the site, not a gap in our knowledge; noted here so we don't lose it. Full detail in the 2026-07-03 scan below. - Computational lower bounds on any counterexample** (Alfaiz's comment): K. Markström [Ma04] — any *cubic* counterexample needs $\geq 30$ vertices. Nowbandegani & Esfandiari [NoEs11] — any *bipartite* counterexample needs $\geq 32$ vertices. UPDATE 2026-07-02 (ours, verified): exhaustive dual-oracle search over ALL connected min-degree-3 C4-free graphs — any counterexample needs $\geq 20$ vertices (n=17: 34,758,006; n=18: 834,711,846, count-certified; n=19: 22,816,929,306; zero candidates). Details: Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02). Full 2026-07-02 campaign (GP≤2000, no necklace gadget ≤18, named high-girth graphs): Erdős #64 — full exclusion campaign 2026-07-02: n≤19, GP≤2000, no necklace gadget ≤18, high-girth named graphs. ALSO (ours, 2026-07-02): no vertex-transitive counterexample up to 1280 vertices — full Potočnik–Spiga–Verret census swept (111,360 graphs, all contain a power-of-2 cycle): Erdős #64 — no vertex-transitive counterexample up to 1280 vertices (census sweep, 2026-07-02). Any counterexample is asymmetric or >1280 vertices. Nowbandegani, Esfandiari, Haghighi & Bibak [NEHB14] — any *cubic claw-free* counterexample needs $\geq 114$ vertices, and every claw-free graph with min degree $\geq 3$ has a cycle of length $2^k$ or $3\times 2^k$ for some $k$. - Structural constraint on any minimal counterexample (2026): A. Carr [Ca26b], arxiv.org/abs/2605.22844 ("Every Minimal Counterexample to the Erdős-Gyárfás Conjecture is Predominantly Cubic," submitted 13 May 2026): building on Markström's structural observation, shows every vertex of a minimal counterexample is adjacent to a degree-3 vertex, and $\geq 4/7$ of its vertices have degree exactly 3; every *regular* minimal counterexample must be cubic. Narrows the search space, does not resolve. - No AI/formal-proof resolution: the DeepMind formal-conjectures Lean stub for this problem (github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/64.lean, fetched directly) is tagged category research open with theorem erdos_64 : answer(sorry) ↔ ... := by sorry — i.e. formalized as a statement but with no proof, confirming open status as of the repo's last update. - Related problems: Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often (chromatic-number analogue, PROVED by the same [LiMo20] paper), Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) (Erdős–Hajnal cycle-length-reciprocal-sum problem, sharp bound also from [LiMo20], second half still open).

Literature state

Not resolved for the stated (tight, minimum-degree-exactly-3) case. Direct fetch of erdosproblems.com/64 (no HTTP error this pass) confirms status = OPEN, with "there are no solutions, partial or complete, claimed in the comments."

The single most important literature fact, previously missed: the general/asymptotic version of this problem IS resolved. Liu & Montgomery, arXiv:2010.15802 ("A solution to Erdős and Hajnal's odd cycle problem," JAMS 2023) prove that once average (hence minimum) degree exceeds some *absolute, degree-independent* constant, a graph is forced to contain cycles of every even length in a wide range $[(\log \ell)^8,\ell]$ — hence certainly a power-of-2 cycle. This (a) directly refutes the Erdős–Gyárfás belief that the conjecture should be *false* and moreover false-for-arbitrarily-large-minimum-degree, and (b) fully resolves the chromatic-number sibling problem Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often via de Bruijn–Erdős, and (c) gives the sharp asymptotic constant for Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree). What remains genuinely open is only the narrow boundary case: minimum degree exactly $\geq 3$ (as opposed to "$\geq$ some large absolute constant").

Progress since then is almost entirely case-by-case structural: an actively growing "$P_t$-free" induced-forbidden-path line ($P_8$ 2022 → $P_{10}$ 2024, both explicitly reducing to "cycle of length 4 or 8"), a parallel diameter/claw-free/Cayley-graph line, and (May 2026, very recent, ~2 months before today) Carr's structural pruning result forcing any minimal counterexample to be almost-cubic. No paper claims a proof or counterexample of the full statement. The site's own comment thread (Alfaiz, Dec 2025) is the most current and comprehensive secondary source and explicitly frames all of the above as still leaving the conjecture open.

No mention of GPT/DeepMind/Aristotle-style AI-assisted resolution was found for this specific problem; the DeepMind formal-conjectures repo has only formalized the statement (with sorry), not proved it.

Attack surface

- Mode: finite-search (primary, since falsifiable) + literature-resolution (the $P_t$-free line is still actively moving and Carr's 2026 "predominantly cubic" result is a fresh pruning tool for both proof and search) - Concrete first experiment: exhaustive generation via nauty's geng -c -d3 (connected, min degree $\geq 3$) restricted first to cubic graphs (geng -c -d3 -D3, guided by Carr's 2026 result that minimal counterexamples are $\geq 4/7$ degree-3 and every vertex touches a degree-3 vertex) for $n$ from 18 up past Markström's known-safe 30-vertex cubic bound; for each graph run a cycle-length-spectrum check (only lengths 4, 8, 16 matter up to $n \leq 31$) and flag any graph with cycle-length set $\cap \{4,8,16,32,\dots\} = \emptyset$. - Oracle: mechanical — full cycle-length spectrum via exact enumeration (networkx.simple_cycles or DFS with early termination) for $n \lesssim 30$; cross-check candidate counterexamples in a second independent tool (nauty/plantri regenerated vs. networkx) before trusting a result. - Feasibility: full resolution is out of reach (30+ year old conjecture, actively worked by multiple groups, now further narrowed by Liu–Montgomery to only the tight min-degree-3 boundary). A realistic first contribution is (1) reproduce/extend Markström's ~20-year-old 30-vertex cubic / 32-vertex bipartite exhaustive bounds with modern SAT/nauty tooling, now specifically pruned by Carr's May-2026 "predominantly cubic" constraint — this is a genuinely re-runnable, citable computational artifact; or (2) push the $P_t$-free literature line past $P_{10}$ (current frontier per Alfaiz's comment) as a derivation/formalization target, since that line's proofs are short, structural, and have a clear repeatable pattern (forbidden induced path $\Rightarrow$ structural decomposition $\Rightarrow$ cycle of length 4 or 8 exhibited directly).

Related

- Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often — chromatic-number analogue ("infinite chromatic number $\Rightarrow$ cycle of length $2^n$ for infinitely many $n$"); PROVED, by the same [LiMo20] paper via de Bruijn–Erdős + Theorem 1.1, explicitly cross-linked on erdosproblems.com/63 ("See also [64]"). - Erdős #65 (part 1) — Erdős–Hajnal: sum of reciprocal cycle lengths ≫ log(minimum degree) — Erdős–Hajnal sum-of-reciprocals-of-cycle-lengths problem ($\sum 1/a_i \gg \log k$); the $\geq(\tfrac12-o(1))\log k$ sharp bound comes from the same [LiMo20] paper; second half (is complete bipartite the minimizer?) still open. - Large min/average degree forces a wide interval of cycle lengths (Liu–Montgomery robust-expander embedding) — the Liu–Montgomery machine: sufficiently large average degree forces cycles of every even length in a wide interval $[(\log \ell)^8, \ell]$; the technique that resolved erdos/63, gave the sharp bound for erdos/65, and bounds the general form of erdos/64. - SAT/CP-SAT-based finite counterexample search and verification — CP-SAT/SAT-based candidate generation and verification for a finite counterexample search. - nauty/geng/plantri: canonical-construction-path exhaustive generation of graphs (min-degree / cubic / planar families) — geng/plantri exhaustive generation of min-degree-3 / cubic graphs up to $n=N$; the tool underlying Markström's 30-vertex and Royle's 17-vertex bounds. - Discharging method — charge-counting technique for planar/structural graph coloring and cycle-existence proofs — technique used by Heckman & Krakovski (2013) for the 3-connected cubic planar case. - P_t-free graphs: the Gyárfás path argument (χ-boundedness + minimal-counterexample cycle surgery) — the $P_t$-free ($K_{1,m}$-free, claw-free, etc.) restricted-class proof line ($P_8 \to P_{10}$), each reducing to "exhibit a cycle of length 4 or 8." - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) — Markström's/Carr's degree-3-adjacency and $4/7$-cubic pruning of any hypothetical minimal counterexample (arXiv:2605.22844).

COMPLETE PRIOR-ART SCAN (2026-07-03)

Triggered by an actual mistake: we previously claimed novelty for 24-vertex $P_{18}$-free, $C_4/C_8$-free witnesses that were already sitting in the special-graphs branch of github.com/rbsandeep/Erdos-Gyarfas. This scan was done by two independent research agents (one focused on GitHub/arXiv computational prior art, one on erdosproblems.com's live site/forum/AI-tracking) to find out, with primary-source evidence, exactly what is and isn't claimed before we publish anything. Both agents fetched and read primary sources directly (not just search snippets); every claim below is sourced to a URL that was actually fetched.

Q1 — Has the "4-or-8" $P_t$-free line been pushed to $P_{14}$+ by anyone?

No — genuinely unclaimed, and there is actually more headroom than we thought. The full text of arXiv:2410.22842v2 (Hegde, Sandeep & Shashank, revised 11 Feb 2025; https://arxiv.org/pdf/2410.22842) was read directly, and it proves two different statements with two different implementations that stop at two different $t$ values — this distinction was previously being conflated:

- Theorem 1 (general conjecture — cycle of *any* power-of-2 length): proven for $P_{13}$-free graphs. $k=3..13$ ran serially (11h56m for $k=13$); the parallel Cilk run OOM'd at $k=14$. This is the "OOM at $P_{13}$/$P_{14}$" fact we already knew. - Theorem 2 (the *specific* "cycle of length 4 or 8" statement — the one we actually care about): uses a separate implementation (the 4-8-cycles branch of the same repo) and is only proven for $P_{12}$-free graphs (3h9m at $k=12$). Quote from the paper: *"We have a different implementation of the algorithm in which only cycles of lengths 4 and 8 are forbidden (see the branch '4-8-cycles')... Using this, we obtain a stronger result for $P_{12}$-free graphs."* No $k=13$ or $k=14$ run is reported anywhere for this 4-8-only variant.

So the actual published frontier for the 4-or-8-specific statement is $P_{12}$, not $P_{13}$ — meaning $P_{13}$ itself is already unclaimed for that statement, and $P_{14}$ even more so. The paper explicitly poses $P_{14}$ as an open question, not a result: *"We end with the following question: Is Algorithm 1 capable of resolving the conjecture for $P_k$-free graphs for every integer $k \geq 14$?"*

All 6 branches of github.com/rbsandeep/Erdos-Gyarfas were enumerated via the GitHub API (branches list + recursive tree + README on each, all last touched Feb 8–10 2025, no activity since):

| Branch | Contents | $P_t$ data beyond paper | |---|---|---| | main | Theorem-1 (general) C++ source | none | | cilk | Cilk-parallel Theorem-1 source | none | | 4-8-cycles | Theorem-2 (4-or-8-only) C++/Cilk source | none — no logs past $P_{12}$ | | logs | Manual verification logs, $k=3..5$ only | none | | tests | Unit tests | N/A | | special-graphs | 24/28-node witness graphs (see Q2) | witnesses only, not a $P_{14}$+ proof |

No other group/paper was found working this specific line (checked DBLP for R.B. Sandeep — no 2025/2026 follow-up beyond the arXiv v1/v2; checked broad arXiv/web search for "$P_{14}$-free" + Erdős–Gyárfás — nothing). Conclusion: an exhaustive proof of $P_{14}$-free (or even $P_{13}$-free) for the specific 4-or-8 statement is unclaimed by anyone as of 2026-07-03, provided our own method is actually proving the 4-or-8-specific statement (Theorem 2's target) and not silently doing weaker/different work — worth double-checking our own scope against the paper's Theorem 2 definition before we publish.

Q2 — Is the $P_{17}$ ceiling stated in a PAPER, or only sitting as data files?

It is in the paper's own prose — this is exactly the same trap as before, now confirmed in the actual published text, not just the repo. arXiv:2410.22842's appendix (item 4) states verbatim: *"We obtained all the four cubic graphs with minimum number (24) of vertices (found by Markström) having no 4-cycle and no 8-cycle but having a 16-cycle... Only one of them, known as Markström graph, is planar. It is $P_{18}$-free but has an induced $P_{17}$."* This traces back to Markström's original 2002/2004 construction, reproduced (not newly discovered) by Hegde et al. in the special-graphs branch (24-node-cubic-no-4-8-cycles-p18-free.{1,2,3}.txt, README: *"This branch contains special graphs that do not have 4 to 8 cycles but contain 16 cycles... reproduced four graphs from the paper that contains Markström Graph."*).

There is also a second, even further data point already public in the same branch: a 28-node cubic graph that is $P_{21}$-free (28-node-cubic-no-4-8-cycles-p21-free.txt) — an even weaker/further ceiling, superseded by the tighter 18-vertex one but worth knowing about so it doesn't surprise us later.

Conclusion: the "4-or-8 statement fails for $t \geq 18$" ceiling is fully public, in paper text, since Feb 2025. Nothing to claim here — this is prior art, not our result, and must be cited as such, not "discovered."

Q3 — Best PUBLISHED computational lower bound on a general (non-cubic) min-degree-3 counterexample?

17 vertices, unimproved since 2002/2004. Source: Klas Markström, "Extremal graphs for some problems on cycles in graphs," Congressus Numerantium 171 (2004), 179–192 (tech-report precursor: Umeå Dept. of Mathematics, 2002, http://abel.math.umu.se/~klasm/Uppsatser/cycex.pdf). Hegde et al.'s own paper cites it directly: *"Extensive computer searches have been done to show that a counterexample has at least 17 vertices, a cubic counterexample has at least 30 vertices [10]."* Cross-checked against Wikipedia's Erdős–Gyárfás page (stale, last edited Jul 2024, still says 17) — no contradiction found. No paper or repo from 2015–2026 improving this general bound was located by either agent, despite broad searching (nauty/geng-based search terms, nauty exhaustive counterexample search, etc.).

Two adjacent/specialized bounds, flagged for precision, not to be confused with the general bound: cubic $\geq 30$ (Markström, same source — matches what's already in our Facts section); bipartite $\geq 30$ or $\geq 32$ depending on source (Hegde et al. cite 30 for bipartite via [Nowbandegani–Esfandiari 2011]; other secondary snippets say 32 — unresolved discrepancy, the primary Nowbandegani–Esfandiari text could not be fetched directly by either agent; flagged, not blocking, since it's not the general bound we care about). Cubic claw-free $\geq 114$ (Nowbandegani et al.) surfaced only in secondary snippets, not independently verified against a primary source this pass — treat as unconfirmed pending direct fetch.

Also worth knowing: Google DeepMind's AlphaEvolve paper (arXiv:2511.02864, Georgiev/Gómez-Serrano/Tao/Wagner, v3 Dec 2025), §6.31/§31 "Erdős–Gyárfás conjecture" (their internal Problem 51), states verbatim: *"we experimented with tasking AlphaEvolve to produce a counterexample to the conjecture by optimizing a score function... We experimented with graphs up to 40 vertices, but ultimately did not find a counterexample."* This is a heuristic/evolutionary search, not an exhaustive proof — it does not establish a rigorous 40-vertex lower bound and carries no formal weight, but it means Tao's own group already poked at exactly this question non-exhaustively up to $n=40$ and found nothing, which is worth citing for context/differentiation (our search is exhaustive; theirs was heuristic) and worth checking our own method doesn't quietly duplicate their (published, public-code) approach: github.com/google-deepmind/alphaevolve_repository_of_problems/blob/main/experiments/erdos_gyarfas_conjecture/erdos_gyarfas_conjecture.ipynb.

Conclusion: our exhaustive ≤19-vertex result (no counterexample found among all connected min-degree-3 $C_4$-free graphs on $n \leq 19$, i.e. any counterexample needs $\geq 20$ vertices) would be a genuine 2-vertex improvement over a 20+ year old published record (17 vertices, Markström 2002/2004) — provided our own search is in fact exhaustive and correct (that verification is outside the scope of this prior-art scan). This is, on current evidence, our strongest genuinely-unclaimed result.

Q4 — Full erdosproblems.com/64 comment/forum thread — anything missed?

Fetched directly (curl with browser UA, HTTP 200 — no blocking issue this pass). Exactly one comment exists: Alfaiz, 06 Dec 2025, 👍1 📝1 🤖0 reactions (the 🤖 icon is the site's own "AI attempts" counter, reading zero — see Q5). No comment newer than 06 Dec 2025. The page itself carries a note: *"This page was last edited 10 April 2026 (The site has been updated to address this comment.)"* — i.e. Bloom folded Alfaiz's literature list into the static page body between Dec 2025 and Apr 2026; that's why our existing Facts section already reads like a merged version of the comment.

Both erdosproblems.com/forum/thread/64 and erdosproblems.com/forum/discuss/64 resolve (HTTP 200) but render the identical content to /64 plus the same single comment — they are just the "discussion view" of the same page, not a separate conversation. erdosproblems.com/forum/64 404s.

One real gap found: erdosproblems.com's own literature list (main page + Alfaiz's comment) does not cite arXiv:2410.22842 (Hegde–Sandeep–Shashank) anywhere, even though it's a stronger published result ($P_{13}$-free general / $P_{12}$-free 4-or-8) than the $P_{10}$-free result [HuSh24] the site does cite. No retraction/erratum was found for the Hegde et al. paper, so this looks like a genuine oversight on Bloom's part, not a quality problem with the paper. We've now added it to our own Facts section (item ix above) so we don't lose it.

Conclusion: nothing missed on the erdosproblems.com side beyond what's already in our Facts/Literature-state sections; the one new thing found is that WE were missing the arXiv:2410.22842 citation (now fixed above), and that the official site is also missing it.

Q5 — Any AI-system contribution to #64 logged anywhere?

No formal log exists, but there is one real (unlogged) AI attempt. Checked: (a) the problem's own 🤖 AI-attempts counter on erdosproblems.com/64 reads 0; (b) github.com/teorth/erdosproblems/wiki/AI-contributions-to-Erdős-problems (data as of 30 Jun 2026) has no mention of "64," "Erdős–Gyárfás," or "power of two/2"; (c) the site's global forum/thread/AI Contributions megathread (1.48MB, grepped exhaustively) has zero matches for #64 or Gyárfás, while neighboring problems #60, #62, #65 do appear there.

The one real exception: AlphaEvolve did attempt #64 (see Q3 above, arXiv:2511.02864 §6.31) — tasked to find a counterexample by score-function optimization, searched graphs up to 40 vertices, found nothing. This attempt is not logged anywhere on erdosproblems.com despite Terence Tao being both the site owner and a co-author of the AlphaEvolve paper — apparently never cross-posted into his own tracker for this problem. Worth citing as the one genuine (negative, heuristic) AI contribution that exists, while being clear it is un-logged and non-exhaustive.

Q6 — Is the conjecture believed true or false now? Any shift in expert opinion?

No explicit, sourced belief-shift found — the site still states the original pessimistic framing verbatim, unchanged as of the 10 April 2026 edit. Erdős and Gyárfás originally believed the conjecture is false, and moreover that no minimum-degree threshold would ever force a power-of-2 cycle. That *stronger* claim was already disproved by Liu–Montgomery (arXiv:2010.15802, JAMS 2023) — old news, already in our Facts section — but neither erdosproblems.com, nor Wikipedia, nor any forum post, nor any 2025/2026 paper commentary was found asserting a broader consensus shift toward TRUE for the narrow min-degree-exactly-3 case. The accumulating evidence (Carr's diameter-2 and predominantly-cubic results, Hegde et al.'s $P_{12}$/$P_{13}$-free results, AlphaEvolve's failed 40-vertex heuristic search, Markström's 17-vertex bound, and now potentially our own ≥20-vertex bound) all point the same direction — no small/structured counterexample exists — but this is *our* inference from the accumulated data, not a documented shift in the field's stated belief. If we publish a true-vs-false opinion, we would be the first to state it explicitly as a synthesis, not reporting an existing consensus.

Bottom line for us

1. $P_{14}$-free (and even $P_{13}$-free) for the specific 4-or-8 statement is genuinely unclaimed — published frontier for that exact statement is $P_{12}$ (Hegde–Sandeep–Shashank, arXiv:2410.22842, 4-8-cycles branch), not $P_{13}$ as we'd assumed; $P_{13}$ is only proven for the *general* power-of-2 statement (different theorem, different implementation). We should explicitly frame any claim as "first proof for $P_{14}$-free (4-or-8-specific)" and cite the $P_{12}$ frontier precisely, not conflate it with the $P_{13}$-OOM anecdote. 2. The $P_{17}$/$P_{18}$ ceiling is fully public, in paper prose, since Feb 2025 — not just repo data, and not ours to claim. Must cite Hegde et al.'s appendix + Markström's original construction, not present as a discovery. 3. Our ≤19-vertex exhaustive bound (⇒ counterexample needs ≥20 vertices) is, on current evidence, a genuine 2-vertex improvement over the 20-plus-year-old published record of 17 vertices (Markström 2002/2004) — nobody found to have improved it since, though AlphaEvolve did a non-exhaustive heuristic check up to 40 vertices in 2025 that should be cited for context/differentiation. 4. No AI-contribution log exists for #64 on erdosproblems.com; the one real AI attempt (AlphaEvolve, negative, non-exhaustive, up to 40 vertices) is undocumented there and should be cited by us. 5. No documented expert belief-shift toward TRUE exists yet — if we state one, we're originating it, not reporting it.