Albertson–Berman Induced Forest Conjecture

Albertson and Berman conjectured that for every simple planar graph $G$ on $n$ vertices, the largest vertex set inducing a forest has size at least $n/2$ . The standing lower bound since the same year has been Borodin's $2n/5$ , from his acyclic five-colour theorem. False: there is an explicit $31$ -vertex simple $3$ -connected maximal planar graph $T$ whose largest induced forest has exactly $15$ vertices, and an infinite family $M_k$ on $31k$ vertices with induced-forest number exactly $15k$ , giving the ratio $15/31 < 1/2$ even for triangulations of minimum degree five.

Result: Disproved(see note)
Status: Resolved
AI contribution: AI co-developed
Method: Construction
Field: Graph theory
Posed by: Michael O. Albertson, David M. Berman
Year posed: 1979
Years open: 47y
Solved: 2026-08-11
Model: GPT-5.6 Sol
Vendor: OpenAI
Collaborators: Heejae Jung
Verification: Site-confirmed
Publication: Preprint
Significance: 30 / 100
Disclosed cost: —
Wikipedia: Not counted (article postdates the solution)

What was actually shown

The ratio 15/31 is not claimed to be optimal, and the paper makes no claim that 31 vertices is the smallest possible counterexample. The construction produces separating triangles by design, so it says nothing about the 4-connected case.

What the AI did

The paper's "Acknowledgments and AI disclosure" section states that the two-terminal gadget "was discovered, and substantial parts of the proof strategy were developed, through interaction with OpenAI GPT-5.6 Sol", while the author "selected the research problem, directed the computational search and subsequent proof development, and checked the resulting mathematical arguments and computational certificates". GPT-5.6 Sol also assisted in preparing the manuscript and the verification code.

Verification

Reproduced by this site on 12 August 2026. The refutation is a single finite object, so it is checkable outright rather than on trust. We rebuilt the 31-vertex seed T from the paper's own definitions - the 14-vertex gadget's cyclic neighbour lists, the pentagonal-bipyramid base, the decorated rim edges 01 and 23, the stated vertex labelling, and the two completion edges 6-12 and 6-20 - without running the author's code. That yields a simple 3-connected planar graph with 31 vertices and 87 = 3n-6 edges, hence a triangulation, with the paper's degree multiset 4^1 5^17 6^6 7^7. Its maximum induced forest was then computed exactly by two independent algorithms: an ILP with lazy cycle-elimination cuts, and a branch-and-bound minimum feedback vertex set with no LP involved. Both give a(T) = 15, equivalently a minimum feedback vertex set of exactly 16, against the 15.5 the conjecture requires. We separately brute-forced the two finite inputs to the symbolic argument - the terminal profile (6,6,6,5) over all 2^12 internal subsets, and beta = 3 over all 2^7 subsets of the seven-vertex core - and confirmed that J plus the edge bf is the icosahedral graph, that the paper's 15-vertex witness induces the stated path, and that M_k for k = 2..5 is planar on 31k vertices with 93k-6 edges, minimum degree five, and every seed induced. Worth noting what the author's shipped verifier does not do: it certifies the gadget embedding, the profile, beta and the sphere certificates, but it never computes a(T) or a(M_k) and says so. That computation is the one this site supplied. The preprint is not peer-reviewed, is not on arXiv, and no independent expert has reviewed it; site-confirmed here means the counterexample is finite and we checked it ourselves, not that the community has weighed in.

Sources

Submitted by MellowWalrus138 on 12 Aug 2026

Albertson–Berman Induced Forest Conjecture

What was actually shown

What the AI did

Verification

Sources

Discussion