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.