← All problems

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.

References

Progress summary

Refreshed
Open · solution reported

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

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.

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.

Sources

Solutions 0

No solutions have been posted yet.