A 15/31 Counterexample Family to the Albertson-Berman Conjecture

Abstract

For a graph $G$, let $a(G)$ be the maximum number of vertices in an induced forest. The Albertson-Berman conjecture, posed in 1979, asserts that every $n$-vertex planar graph satisfies $a(G)\ge n/2$. Borodin's bound $a(G)\ge 2n/5$ remains the general lower bound toward this problem. We disprove the conjecture with an explicit 31-vertex plane triangulation $T$ satisfying $a(T)=15$. Moreover, for every integer $k\ge2$, we construct a simple planar graph $M_k$ with $|V(M_k)|=31k$ and $a(M_k)=15k$, so that $a(M_k)/|V(M_k)|=15/31<1/2$. Every member of the family has minimum degree five. The construction starts from a $31$-vertex seed obtained by substituting a $14$-vertex two-terminal gadget into a pentagonal bipyramid, and then uses annular joins along facial triangles to preserve the exact ratio. The resulting graphs are sphere triangulations, and hence maximal planar.

Disclosure

“is the minimum within our construction; smaller counterexamples from other constructions may well exist. 8 Acknowledgments and AI disclosure The initial gadget and several proof ideas emerged from exploratory sessions with OpenAI’s GPT- 5.6 Sol, which also assisted in preparing the manuscript and verification code. The author is responsible for the problem selection, the mathematical verification, and the final form of all proofs, and assumes full responsibility for”

PDF page 11

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:21:27.414299Z

Structural counts