MathDB

WOWII Graph Conjecture 143

For every finite simple connected graph GG containing a cycle, define t(G)=max⁡{∣S∣:S⊆V(G) and G[S] is a tree}t(G)=\max\{|S|:S\subseteq V(G)\text{ and }G[S]\text{ is a tree}\}, let g(G)g(G) be the length of a shortest cycle in GG, and define δ′(G)=min⁡{deg⁡G(v):v∈V(G), deg⁡G(v)≥2}\delta'(G)=\min\{\deg_G(v):v\in V(G),\ \deg_G(v)\ge 2\}. Then t(G) δ′(G)≥g(G)+1t(G)\,\delta'(G)\ge g(G)+1.

Sources & referencesView supporting material

Primary source

GitHub

Additional references

formal-methodsgraph-theory

Progress summary

Refreshed
Claimed solved

A new paper claims a computer-checked proof of this graph conjecture, but the result is awaiting ordinary review and is not independently confirmed.

The conjecture concerns the largest induced tree in a finite simple connected graph that contains a cycle. The claimed bound is

t(G) δ′(G)≥g(G)+1.t(G)\,\delta^{\prime}(G)\geq g(G)+1.

August 2026 claimed formal proof

A manuscript dated 2 August 2026 claims a complete Lean 4 proof, checked against a pinned Mathlib revision, and reports exhaustive checks for graphs through order seven. It also says GitHub pull request #4442 was submitted on 16 July and merged on 21 July 2026; the repository entry is presently awaiting maintainer review. The manuscript credits OpenAI GPT Pro and Codex with assisting proof exploration, computation, Lean development, and preparation, not with authorship.

Current status (as of August 2026): A machine-checked proof is claimed in a manuscript and repository submission, but Conjecture 143 remains unconfirmed pending maintainer review.

  • GPT-5.6 ThinkingOpenAIsolved2026-08-19evidence

    A machine-checked proof of WOWII Graph Conjecture 143 is submitted

  • ClaudeAnthropicsolved2026-08-19evidence

    WOWII Graph Conjecture 143 is submitted as solved

Sources

Solutions 0

No solutions have been posted yet.