Large induced forest in a planar graph.

Large induced forest in a planar graph.

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple planar graph on $n$ vertices. For $U\subseteq V$, its induced subgraph $G[U]$ has vertex set $U$ and all edges of $G$ whose ends lie in $U$. A forest is an undirected graph with no cycle; it may have several components and isolated vertices. Define \[ a(G)=\max\{|U|:G[U]\text{ is a forest}\}. \] The Albertson--Berman conjecture in this record is that \[ a(G)\ge\frac n2 \] for every finite simple planar graph. In integer terms this requires at least $\lceil n/2\rceil$ vertices.

Equivalently, one should be able to delete a set $S\subseteq V$ of at most $\lfloor n/2\rfloor$ vertices meeting every cycle. Such a set is a feedback vertex set, and $G-S$ must retain every edge between the remaining vertices. Selecting a spanning forest by simply removing edges is therefore insufficient: a forest subgraph on all vertices need not be induced.

The conclusion asks for one large induced forest, without requiring that the complementary vertices also induce a forest. No girth, maximum-degree, or connectedness assumption accompanies planarity. The factor one half cannot be increased uniformly: a disjoint union of copies of $K_4$ is planar and contributes at most two vertices per copy to an induced forest, since every three vertices of a $K_4$ already form a cycle. All bounds concern the number of vertices rather than edges.

Short English statement

Can at least half of the vertices of every planar graph be retained while the induced graph has no cycle?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 2 October 2026. The canonical formulation above is retained. This attempt uses a primary-source literature audit, independent restricted proofs, and adversarial checks. Reproved results are not claimed as new. Numerical tests below are reproducible in scripts/check_attempt_batch03_extremal_2026_10_02.py.

Literature correction and scope.

The catalogue records the Albertson--Berman half-order conjecture. It must not be described as currently open without qualification: Cames van Batenburg, Goedgebeur and Jooken [S3], posted 24 August 2026, report that it has been disproved, determine minimum counterexample order 29, and construct an infinite family with maximum induced-forest order at most $25n/52$. Their complete counterexample computation is not reproduced here. This attempt independently proves a substantial restricted case and identifies a necessary structural feature of any counterexample. The unresolved attempt status refers to our own complete verification, not to the historical conjecture's literature status.

A degeneracy criterion proved constructively.

A graph is $d$-degenerate if every nonempty subgraph has a vertex of degree at most $d$. We prove that every $(2s-1)$-degenerate graph has a partition into $s$ induced forests. Delete vertices one by one with current degree at most $2s-1$, then insert them back in reverse order. At the moment a vertex $v$ is inserted, it has at most $2s-1$ already inserted neighbours. If each of the $s$ classes contained at least two of these neighbours, there would be at least $2s$ such neighbours. Hence some class contains at most one.

Assign $v$ to that class. Its induced subgraph was a forest by induction. Adding a vertex with at most one neighbour in that forest cannot create a cycle: a cycle through the new vertex would require two incident edges within the class. Other classes are unchanged. Induction proves the partition, and its largest class has at least $\lceil n/s\rceil$ vertices. In particular every 3-degenerate graph has an induced forest on at least $\lceil n/2\rceil$ vertices. This is a statement about induced subgraphs, since all edges between vertices of a chosen class are retained throughout.

Applying the criterion to planar graphs.

Every triangle-free simple planar graph is 3-degenerate. To see this, take any nonempty subgraph. If it has at most two vertices, the degree conclusion is immediate. Otherwise the planar triangle-free edge bound $m\le2n-4$ gives average degree less than four, so some vertex has degree at most three. For disconnected subgraphs the same conclusion follows componentwise; the familiar edge bound can also be proved by Euler's formula after separately treating tree components. Thus the desired half-order statement holds for every triangle-free planar graph.

For arbitrary simple planar graphs, Euler's edge bound instead ensures 5-degeneracy, and the same argument gives a partition into three induced forests and an induced forest of order at least $\lceil n/3\rceil$. This is only an elementary lower bound, not a claim to the best bound in the literature. The difference between at most three and at most five previously inserted neighbours is exactly where the two-class proof ceases to work.

Structural and sharpness checks.

If a graph violates the half-order bound, it cannot be 3-degenerate. It therefore has a nonempty subgraph of minimum degree at least four; equivalently its 4-core is nonempty. This is a necessary condition, not a sufficient recipe for a counterexample. For example, the octahedral graph has minimum degree four but an induced three-vertex path and no larger induced forest, giving equality at six vertices. Disjoint copies of $K_4$ also attain exactly one half: three vertices of a block already make a triangle, while two are always permitted.

A proper four-colouring is insufficient by itself. The union of two independent colour classes is bipartite, but bipartite induced subgraphs can contain cycles, as $K_{2,2}$ demonstrates. Thus grouping colour classes does not replace the degeneracy argument. The script checks the constructive two-forest partition on every 3-degenerate labelled graph of order at most five and verifies the stated extremal small examples by exhaustive induced-subset tests.

Final status.

The half-order conclusion is independently established for all 3-degenerate graphs, including triangle-free planar graphs. The unrestricted historical claim is reported disproved by [S3]; this attempt has not independently reconstructed that full disproof. Its own full-target verification is therefore UNRESOLVED, with the precise gap being verification of a cited planar counterexample rather than a missing proof of a true universal theorem.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3312 (OPG-46634), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Large induced forest in a planar graph.. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/large_induced_forest_in_a_planar_graph.
• S3 W. Cames van Batenburg, J. Goedgebeur and J. Jooken, Counterexamples to the Albertson--Berman conjecture: minimum order, connectivity and an improved ratio bound, arXiv:2608.23260v1, 24 August 2026. Literature disproof report, not a counterexample certified by this attempt. https://arxiv.org/abs/2608.23260.