What was already known
Albertson and Berman conjectured that every simple planar graph has an induced forest on at least half its vertices. Earlier multigraph examples did not refute the simple-graph claim; later human examples improve the ratio or graph order.
AI involvement
Jung credits GPT-5.6 Sol with the initial two-terminal gadget and several proof ideas. Jung selected the problem, verified the mathematics and completed the family proof.
GPT-5.6 Sol supplied the decisive two-terminal gadget and several proof ideas under Jung's human direction and final proof development.
Importance
Gives a finite counterexample and an infinite simple-planar family to the 1979 conjecture.
Limitations
Exact optimization checks the 31-vertex seed. The all-k family rests on Jung’s symbolic transfer proof and reported human verification; the construction does not claim an optimal ratio or minimum order.
Technical verification
The finite 31-vertex refutation was exactly checked by independently implemented optimization methods, and Jung reports checking the symbolic arguments that extend it to every k. The final arXiv appendix documents seed optimization; VibeMathed separately reports reproducing the seed and optimum. This is source-reported checking, not a computation repeated in this review.
Formal checking
independent exact branch-and-bound and ILP cycle-cut optimizations, plus planarity and gadget data checks
- Checker
- Jung's final verifier, with independent VibeMathed reproduction of the seed
- Scope
- The explicitly reconstructed 31-vertex planar seed has maximum induced forest exactly 15
- Basis
- Reported by the linked checker
author's mathematical verification of the final symbolic proof
- Checker
- Heejae Jung, author
- Scope
- The gadget transfer law and annular construction yield a(M_k)=15k for every k>=2
- Basis
- Reported by the linked checker
Checking a formal statement does not establish that it matches the original problem.
Human understanding
Jung explains the terminal penalty, substitution accounting, pentagonal-bipyramid obstruction and annular joins in a symbolic proof, showing the mechanism of the retained gadget and family.
Correction and publication history
Gives a finite counterexample and an infinite simple-planar family to the 1979 conjecture.
Read this published revision