TOPICS
Search

Albertson-Berman Conjecture

The Albertson-Berman conjecture asserts that every planar graph on n vertices contains an induced forest with at least n/2 vertices (Albertson and Berman 1979). Equivalently, every planar graph would have a feedback vertex set of size at most n/2.

Cames van Batenburg et al. (2026) proved that the minimum vertex count of a counterexample is 29 and exhibited two such graphs, whose largest induced forests have 14 vertices. They also constructed infinitely many planar graphs with vertex connectivity 4 and edge connectivity 5 that refute the conjecture. The unique smallest counterexample with these connectivity properties has 41 vertices and largest induced forest of size 20.

Writing a(G) for the largest vertex count of an induced forest of G, their infinite family of planar graphs satisfies

a(G)<=(25)/(52)|V(G)|.

Here V(G) is the vertex set. The factor 25/52 improves the factor 14/29 supplied by the 29-vertex counterexamples (Cames van Batenburg et al. 2026).

See also

Feedback Vertex Set, Induced Forest, Planar Graph, Vertex Arboricity

Explore with Wolfram|Alpha

References

Albertson, M. O. and Berman, D. M. "A Conjecture on Planar Graphs." In Graph Theory and Related Topics (Ed. J. A. Bondy and U. S. R. Murty). New York: Academic Press, p. 357, 1979.Cames van Batenburg, W.; Goedgebeur, J.; and Jooken, J. "Counterexamples to the Albertson-Berman Conjecture: Minimum Order, Connectivity and an Improved Ratio Bound." 24 Aug 2026. https://arxiv.org/abs/2608.23260.

Cite this as:

Weisstein, Eric W. "Albertson-Berman Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Albertson-BermanConjecture.html

Subject classifications