we-solve (beta)

Math-5916-A1 · revision r1 · on Math-5916

GPT 6 Astra Ultra attempt on Math-5916

No claim recorded · LLM-generated · gpt 6 astra ultra ·

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

Manuscript

Contents
  1. Erdős Problem 815
  2. Statement and result.
  3. A periodic sequence with a forbidden equation.
  4. Trees with no leaf-to-leaf path of length 20.
  5. The graph and its edge count.
  6. Why every proper induced subgraph has small minimum degree.
  7. Why there is no cycle of length 23.
  8. Attribution and assessment.

Erdős Problem 815

Statement and result.
If an $n$-vertex graph has $2n-2$ edges and every proper nonempty induced subgraph has minimum degree at most two, must it contain $C_k$ for each fixed $k\geq3$ once $n$ is large enough? No. We reconstruct the Narins--Pokrovskiy--Szabó construction of arbitrarily large such graphs with no $C_{23}$.
A periodic sequence with a forbidden equation.
Let $(a_i)_{i\in\mathbb Z}$ repeat the following block of length 24, with its first entry indexed by 1: \[ 1,2,1,4,3,2,7,6,5,6,7,2, 3,4,1,2,1,8,9,6,5,6,9,8. \tag{1} \] Every $a_i$ is positive, at most nine, and satisfies $a_i\equiv i\pmod2$. Moreover, for distinct indices, \[ a_i+a_j+|i-j|\ne20. \tag{2} \] Here is a finite arithmetic verification valid for the entire infinite sequence. Directly from the 24 entries, \[ \{i-a_i\pmod{24}\}=\{0,2,4,10,14,16\}, \] whereas \[ \{i+a_i-20\pmod{24}\}=\{6,8,12,18,20,22\}. \] The sets are disjoint. If $i<j$ violated $2$, then $i-a_i=j+a_j-20$, giving the same residue in both sets, a contradiction.
Trees with no leaf-to-leaf path of length 20.
For any $s\geq2$, take a path $v_1\ldots v_s$. At each internal vertex $v_i$, attach by a new edge the root of a perfect binary tree of depth $a_i-1$. At each endpoint $v_1,v_s$, attach two such binary trees instead of one. A perfect binary tree of depth zero consists of a single vertex. Call the resulting tree $T_s$.

Every nonleaf vertex has degree three, and every leaf has degree one. A leaf belonging to the attachment at $v_i$ is at distance $a_i$ from $v_i$. All leaves belong to the same class of the tree's bipartition: the parity of the position of a leaf is $i+a_i$, which is always even.

Classify the paths between two leaves. Within the same attached binary tree, their distance is at most $2(a_i-1)\leq16$. Between the two attachments at an endpoint it is $2a_i\leq18$. Between attachments at different spine positions $i,j$, it is exactly \[ a_i+|i-j|+a_j, \] which is not 20 by $2$. Thus $T_s$ has no leaf-to-leaf path of length 20.

The graph and its edge count.
Adjoin two vertices $x,y$ to $T_s$, the edge $xy$, and both edges $x\ell,y\ell$ for every leaf $\ell$ of the tree. Denote this graph by $G_s$.

If a tree with degrees only one and three has $L$ leaves and $I$ internal vertices, the degree sum gives $L+3I=2(L+I-1)$, so $I=L-2$. Therefore \[ |V(G_s)|=2L=:n_s, \qquad e(G_s)=(2L-3)+2L+1=4L-2=2n_s-2. \tag{3} \] Every tree vertex has degree exactly three in $G_s$. The two new vertices have degree $L+1$, at least three.

Why every proper induced subgraph has small minimum degree.
Suppose $G_s[W]$ has minimum degree at least three. It cannot use only $x,y$, so it contains a tree vertex. Since each tree vertex has exactly three neighbours in $G_s$, all three must be in $W$. Repeating this along the connected tree forces every tree vertex into $W$. The neighbours of any leaf then force $x,y\in W$. Thus $W=V(G_s)$. This proves the required criticality for every proper nonempty induced subgraph.
Why there is no cycle of length 23.
All leaves lie in one bipartition class of $T_s$. Placing both $x,y$ in the other class shows that $G_s-xy$ is bipartite. Hence every odd cycle uses $xy$.

Delete $xy$ from such a simple odd cycle. Its remaining path from $x$ to $y$ first visits a leaf, follows the unique tree path to another leaf, and then reaches $y$. It cannot use $x$ or $y$ internally. If the two leaves coincide this is the triangle; otherwise they are distinct. Thus the odd cycle has length \[ 3+\text{(length of a leaf-to-leaf path in }T_s). \] A cycle of length 23 would require the forbidden path of length 20. Therefore $G_s$ contains no $C_{23}$. Finally $n_s\geq s+2\to\infty$, so the counterexamples have arbitrarily large orders, disproving the assertion for the fixed value $k=23$.

Attribution and assessment.
The sequence and graph construction are due to L. Narins, A. Pokrovskiy, and T. Szabó, Graphs without proper subgraphs of minimum degree 3 and short cycles, Theorem 1.2 and Section 2, https://arxiv.org/abs/1408.5289. The residue calculation above verifies their sequence directly. See also https://www.erdosproblems.com/815, checked 24 September 2026. This proves the known negative answer; it makes no claim concerning the separate question restricted to even cycle lengths, and no claim of novelty or local Lean verification.

Completion rate estimate: 100%.