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

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\mathrm{/}2$. Borodin’s bound $a(G)\ge 2n\mathrm{/}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\ge 2$, we construct a simple planar graph $M_k$ with $\mathrm{\mid }V(M_k)\mathrm{\mid }=31k$ and $a(M_k)=15k$, so that $a(M_k)\mathrm{/}\mathrm{\mid }V(M_k)\mathrm{\mid }=15\mathrm{/}31<1\mathrm{/}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.