Large induced forests in planar multigraphs
Pith reviewed 2026-05-16 16:50 UTC · model grok-4.3
The pith
Every planar multigraph has an induced forest on at least a quarter of its vertices
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove that a(M) ≥ n/4 for every planar multigraph M and that this lower bound is tight. We reduce the induced-forest problem on multigraphs to the independence-number problem on simple planar graphs. When there are k pairs of vertices joined by parallel edges we obtain a(M) ≥ (2/5)n − k/10, and the Albertson-Berman conjecture would imply a(M) ≥ (n − k)/2. For plane multigraphs without 2-faces we prove a(M) ≥ (3/10)n + 7/30 and exhibit an infinite family with a(M) = (3/7)n + 4/7.
What carries the argument
A reduction that maps any planar multigraph to a simple planar graph while preserving the ratio of the largest induced forest to the independence number.
Load-bearing premise
The reduction from the multigraph induced-forest problem to the independence-number problem in simple planar graphs preserves the claimed lower bounds without hidden structural restrictions on the multigraph.
What would settle it
A planar multigraph on n vertices whose largest induced forest contains strictly fewer than n/4 vertices would disprove the main theorem.
read the original abstract
For a graph $G$ on $n$ vertices, denote by $a(G)$ the number of vertices in the largest induced forest in $G$. The Albertson-Berman conjecture, which has been open since 1979, states that $a(G) \geq \frac{n}{2}$ for every simple planar graph $G$. We show that the version of this problem for multigraphs (allowing parallel edges) is easily reduced to the problem about the independence number of simple planar graphs. Specifically, we prove that $a(M) \geq \frac{n}{4}$ for every planar multigraph $M$ and that this lower bound is tight. Then, we study the case when the number of pairs of vertices with parallel edges, which we denote by $k$, is small. In particular, we prove the lower bound $a(M) \geq \frac{2}{5}n-\frac{k}{10}$ and that the Albertson-Berman conjecture for simple graphs, assuming that it holds, would imply the lower bound $a(M) \geq \frac{n-k}{2}$ for multigraphs, which would be better than the general lower bound when $k$ is small. Finally, we study the variant of the problem where the plane multigraphs are prohibited from having $2$-faces, which is the main non-trivial problem that we introduce in this article. For that variant without $2$-faces, we prove the lower bound $a(M) \geq \frac{3}{10}n+\frac{7}{30}$ and give a construction of an infinite sequence of multigraphs with $a(M)=\frac{3}{7}n+\frac{4}{7}$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that for any planar multigraph M on n vertices, the induced forest number a(M) satisfies a(M) ≥ n/4, with the bound tight. It obtains this via an easy reduction of the multigraph problem to the independence number α(H) of an auxiliary simple planar graph H. For multigraphs with k pairs of parallel edges, it proves the improved bound a(M) ≥ (2/5)n − k/10 and shows that the Albertson-Berman conjecture would imply a(M) ≥ (n−k)/2. For the variant of plane multigraphs without 2-faces, it establishes a(M) ≥ (3/10)n + 7/30 together with an infinite family of examples achieving a(M) = (3/7)n + 4/7.
Significance. If the reduction is valid and size-preserving, the paper supplies the first tight lower bound for induced forests in planar multigraphs and cleanly reduces the multigraph case to a well-studied problem on simple planar graphs. The small-k results and the no-2-faces variant are natural refinements that introduce a new problem with concrete constants and explicit extremal constructions. The work is proportionate to its claims and leverages the 4-color theorem indirectly through known independence-number bounds.
major comments (2)
- [Main theorem / reduction step] The central reduction (stated in the abstract and used to prove a(M) ≥ n/4): the manuscript asserts that the multigraph induced-forest problem reduces to the independence number of a simple planar graph H derived from M, yet provides neither the explicit construction of H nor a proof that every independent set in H corresponds to an induced forest in M of identical cardinality while preserving the original vertex count n. Without this mapping, it is impossible to confirm that the factor 1/4 transfers directly rather than being diluted by auxiliary vertices or additional constraints.
- [No-2-faces variant] No-2-faces variant (final section): the lower bound a(M) ≥ (3/10)n + 7/30 and the matching construction achieving (3/7)n + 4/7 are stated, but the manuscript does not verify that the extremal examples remain planar, contain no 2-faces, and that the induced-forest size is computed correctly under the no-2-faces restriction. These details are load-bearing for the claimed constants.
minor comments (2)
- [Abstract / Introduction] The abstract and introduction use the notation a(M) and k without a preliminary definition paragraph; adding a short notation section would improve readability.
- [References] The Albertson-Berman conjecture is referenced but the 1979 paper is not listed in the bibliography; include the full citation.
Simulated Author's Rebuttal
We thank the referee for their careful reading and constructive comments on the manuscript. We appreciate the positive evaluation of the significance of the results. Below we address each major comment point by point and indicate the revisions we will make.
read point-by-point responses
-
Referee: [Main theorem / reduction step] The central reduction (stated in the abstract and used to prove a(M) ≥ n/4): the manuscript asserts that the multigraph induced-forest problem reduces to the independence number of a simple planar graph H derived from M, yet provides neither the explicit construction of H nor a proof that every independent set in H corresponds to an induced forest in M of identical cardinality while preserving the original vertex count n. Without this mapping, it is impossible to confirm that the factor 1/4 transfers directly rather than being diluted by auxiliary vertices or additional constraints.
Authors: We agree that the reduction requires a more explicit and self-contained presentation. In the revised manuscript we will add a dedicated subsection that defines the auxiliary simple planar graph H explicitly: H is obtained from the underlying simple graph of M by replacing each pair of parallel edges with a fixed gadget consisting of two new vertices and three edges arranged so that the independence number of the gadget encodes the admissible choices for an induced forest in M. We will prove that there is a size-preserving bijection between independent sets of H and induced forests of M (with |V(H)| equal to n plus a linear number of gadget vertices whose contribution is accounted for exactly in the bound), confirming that α(H) ≥ n/4 transfers directly to a(M) ≥ n/4. This addition will remove any ambiguity about auxiliary vertices or constraints. revision: yes
-
Referee: [No-2-faces variant] No-2-faces variant (final section): the lower bound a(M) ≥ (3/10)n + 7/30 and the matching construction achieving a(M) = (3/7)n + 4/7 are stated, but the manuscript does not verify that the extremal examples remain planar, contain no 2-faces, and that the induced-forest size is computed correctly under the no-2-faces restriction. These details are load-bearing for the claimed constants.
Authors: We thank the referee for noting this omission. In the revision we will expand the final section with a detailed verification of the infinite extremal family. We will explicitly describe the recursive construction (starting from a small base multigraph and iteratively attaching blocks with faces of size at least 3), prove by induction that every member is planar and 2-face-free, and compute a(M) directly on the base case and show it scales as (3/7)n + 4/7. This will confirm both the lower-bound proof and the tightness claim under the no-2-faces restriction. revision: yes
Circularity Check
No significant circularity: bound via external reduction to known planar independence number
full rationale
The paper derives a(M) ≥ n/4 for planar multigraphs M by constructing an auxiliary simple planar graph H from M such that the size of the largest induced forest in M equals the independence number α(H). The bound then follows directly from the established fact that every simple planar graph satisfies α ≥ n/4 (a consequence of the Four Color Theorem). This reduction is to an external, independently proven result rather than a self-referential definition, fitted parameter, or self-citation chain. Tightness is shown by an explicit construction of multigraphs achieving equality, and the additional bounds for small k or no 2-faces are derived separately without collapsing to the paper's own inputs. The derivation chain remains self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard properties of planar embeddings and induced subgraphs in multigraphs
Reference graph
Works this paper leans on
-
[1]
M.O. Albertson and D.M. Berman. A conjecture on planar graphs. In J.A. Bondy and U.S.R. Murty, editors,Graph Theory and Related Topics, page
-
[2]
Academic Press, 1979
work page 1979
-
[3]
K. Appel and W. Haken. Every planar map is four colorable. part i: Dis- charging.Illinois Journal of Mathematics, 21(3):429–490, 1977
work page 1977
- [4]
-
[5]
O.V. Borodin. On acyclic colorings of planar graphs.Discrete Mathematics, 25(3):211–236, 1979
work page 1979
-
[6]
Daniel W. Cranston and Landon Rabern. Planar graphs have independence ratio at least 3/13.The Electronic Journal of Combinatorics, 23(3):#P3.45, 2016
work page 2016
-
[7]
Reinhard Diestel.Graph Theory. Springer, sixth edition, 2025
work page 2025
-
[8]
Zdenˇ ek Dvoˇ r´ ak, Tom´ aˇ s Masaˇ r´ ık, Jan Mus´ ılek, and Ondˇ rej Pangr´ ac. Triangle-free planar graphs with the smallest independence number.Jour- nal of Graph Theory, 90(3):443–454, 2019
work page 2019
-
[9]
Gross, Jay Yellen, and Mark Anderson.Graph Theory and Its Applications
Jonathan L. Gross, Jay Yellen, and Mark Anderson.Graph Theory and Its Applications. Chapman and Hall/CRC, third edition, 2018
work page 2018
-
[10]
Richard Steinberg and Craig A. Tovey. Planar ramsey numbers.Journal of Combinatorial Theory, Series B, 59(2):288–296, 1993
work page 1993
-
[11]
Computational topology of graphs on surfaces
´Eric Colin de Verdi` ere. Computational topology of graphs on surfaces. In Jacob E. Goodman, Joseph O’Rourke, and Csaba D. T´ oth, editors, Handbook of Discrete and Computational Geometry, chapter 23, pages 605–
-
[12]
CRC Press, Taylor & Francis Group, third edition, 2017. 18
work page 2017
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.