Albertson–Berman induced-forest conjecture for planar graphs
Follow the latest progress by email.
The Albertson–Berman conjecture states that every n-vertex simple planar graph has an induced forest on at least n/2 vertices. An induced forest keeps all edges between the chosen vertices and contains no cycle.
Why it matters and what counts as progress
Why it matters: It asks how much acyclic structure planarity forces when edges cannot be discarded independently.
What counts as progress: A half-size forest theorem for all simple planar graphs, or an explicit simple planar graph with a rigorously smaller maximum induced forest.
How the problem developed
- 1979 · Conjecture [1]
Michael O. Albertson and David M. Berman Conjectured that every n-vertex planar graph has an induced forest on at least n/2 vertices.
- 18 Aug 2026 · Counterexample [2]
Heejae Jung Exhibited a 31-vertex plane triangulation whose largest induced forest has 15 vertices and extended it to a family with ratio 15/31.
- 24 Aug 2026 · Partial result [3]
Wouter Cames van Batenburg, Jan Goedgebeur and Jorik Jooken Found counterexamples of minimum order 29 and a planar family with induced-forest ratio at most 25/52.
AI contribution
A 15/31 Counterexample Family to the Albertson-Berman Conjecture
Jung constructs a 31-vertex simple plane triangulation with maximum induced forest 15, then simple maximal planar graphs Mₖ with 31k vertices, minimum degree five and maximum induced forest 15k for every k≥2. The ratio 15/31 refutes the Albertson–Berman half-forest conjecture.
Sources
Website timeline
Publication dates and editorial changes.