TOPICS
Search

Induced Forest

An induced forest of a graph is a vertex-induced subgraph that is a forest. Thus a subset S of the vertex set V(G) determines an induced forest precisely when G[S] contains no graph cycle.

For a finite simple graph, the complementary vertex set V(G)\S is then a feedback vertex set. Consequently, the maximum number of vertices in an induced forest is the vertex count minus the feedback vertex set number. The Albertson-Berman conjecture concerned the size of the largest induced forest in a planar graph (Cames van Batenburg et al. 2026).

The induced forest polynomial counts induced forests by their number of vertices.

See also

Albertson-Berman Conjecture, Feedback Vertex Set, Forest, Induced Forest Polynomial, Vertex Arboricity, Vertex-Induced Subgraph

Explore with Wolfram|Alpha

References

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. "Induced Forest." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/InducedForest.html

Subject classifications