Pith. sign in

REVIEW 4 major objections 4 minor 23 references

Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound

T0 review · 4 major / 4 minor · reviewed 2026-08-28 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that the smallest planar graph whose largest induced forest has fewer than half of its vertices has exactly 29 vertices, and it improves the best known induced-forest ratio bound to 25/52.

desk verdict The paper settles the natural extremal questions left by the Albertson-Berman disproof, but the exact threshold claims rest on a 10 CPU-year computation that is not yet auditable. read the letter →

arxiv 2608.23260 v1 pith:FIUWBXDE submitted 2026-08-24 math.CO

Wouter Cames van Batenburg , Jan Goedgebeur , Jorik Jooken This is my paper · ORCID
classification math.CO MSC 05C1005C4005C4505C85
keywords Albertson-Bermanconjectureinducedforestplanargraphsexhaustivegenerationminimumcounterexampleconnectivityfeedbackvertexset
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The Albertson-Berman conjecture asserts that every planar graph contains an induced forest--a set of vertices whose internal edges form a forest--of order at least half the graph's order. This paper proves the exact threshold: the smallest planar graph for which this fails has $29$ vertices, and it exhibits one such graph with $a(G_{29})=14$. It also shows that the conjecture fails for highly connected planar graphs, with the smallest $4$-connected, $5$-edge-connected counterexample on $41$ vertices, and it pushes the best upper bound on the guaranteed ratio down to $\frac{25}{52}$. That family also disproves a stronger bounded-degree conjecture for every degree bound $d \geq 7$.

What carries the argument

The argument rests on two mechanisms. The first is a pair of small planar gadgets, $Q$ on $14$ vertices and $R$ on $17$ vertices, each obtained by modifying the icosahedron and each carrying a distinguished edge. For a gadget $J$ with distinguished edge $uv$ and a subset $X\subseteq\{u,v\}$, the value $p_J(X)$ is the order of the largest induced forest in $J$ whose intersection with $\{u,v\}$ is exactly $X$; the profile $(8,8,8,9)$ for $R$ is the load-bearing asymmetry, since its ninth vertex is available only when both endpoints of the distinguished edge are kept. The second mechanism is Stein's duality theorem, which states that a planar triangulation admits a partition of its vertices into two induced forests exactly when its dual graph is Hamiltonian. That theorem converts the search for counterexamples into an exhaustive check of nonhamiltonian cubic planar $3$-connected graphs, and the gadget profiles convert the ratio condition $a(G)<|V(G)|/2$ into finite arithmetic that the enumeration can certify.

What would settle it

Independently re-generate the 46- and 50-vertex dual graphs and re-check Hamiltonicity; finding a nonhamiltonian graph missing from the paper's list, or any listed dual whose corresponding triangulation on 27 vertices has largest induced forest of order at most 13 (12 on 25 vertices), would refute the minimum-order theorem.

Watch

Extended reading notes

Core claim

The central result is Theorem 2.5: the minimum order of a counterexample to the Albertson-Berman conjecture is $29$. The witness $G_{29}$ is built by identifying the distinguished edge $xy$ of a $14$-vertex gadget $Q$ with the distinguished edge $bc$ of a $17$-vertex gadget $R$, both mild modifications of the icosahedron. The key profile for $R$ is $(p_R(\emptyset),p_R(\{b\}),p_R(\{c\}),p_R(\{b,c\}))=(8,8,8,9)$, meaning the only way an induced forest in $R$ reaches $9$ vertices is by keeping both endpoints of the distinguished edge; this asymmetry forces $a(G_{29})=14<\frac{29}{2}$. For the lower bound, the paper reduces any hypothetical counterexample on at most $28$ vertices to a planar triangulation on $25$ or $27$ vertices, then applies Stein's theorem: such a triangulation is not a counterexample whenever its dual is Hamiltonian. An exhaustive enumeration of all nonhamiltonian cubic planar $3$-connected graphs on $46$ and $50$ vertices (the duals of those triangulations), with induced-forest orders computed by a feedback-vertex-set solver, rules out every smaller graph. The same dual machinery identifies a unique $4$-connected, $5$-edge-connected counterexample on $41$ vertices, yields infinitely many more by a gluing operation, and a separate $52$-vertex construction from three copies of $R$ around a central vertex has $a(G_{52})=25$, giving $c_P \le \frac{25}{52}$.

Load-bearing premise

The load-bearing premise is that the ten-CPU-year exhaustive computer search over the relevant 46- and 50-vertex dual graphs is complete and exact, so that every planar triangulation on 25 and 27 vertices was in fact checked.

Editorial extensions

If this is right

  • The minimum-order question is closed: any planar counterexample to the Albertson-Berman conjecture has at least 29 vertices, and 29 is attained.
  • The induced-forest ratio constant now lies between 2/5 and 25/52, so roughly 0.4808 is the best known upper bound on the guaranteed ratio.
  • The conjecture fails for 4-connected, 5-edge-connected planar graphs; the unique smallest such counterexample has 41 vertices, and infinitely many exist.
  • For every degree bound at least 7, the bounded-degree induced-forest conjecture is false: the 52k-vertex graphs contain no induced forest of maximum degree at most d larger than 25k vertices.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The edge-identification construction suggests a deficit calculus: chaining or cyclically gluing gadgets with asymmetric profiles like R can transfer and amplify the ratio deficit, so other gluing patterns may yield counterexamples on 30-50 vertices with ratios below 14/29.
  • The dual-enumeration method is not limited to 50 vertices; extending the exhaustive list to larger sizes would determine the next connectivity thresholds, including whether any 5-connected counterexample exists.
  • The 25/52 family uses three copies of R around one central vertex; varying the number of copies or the cyclic arrangement is a testable route toward smaller values of the induced-forest ratio constant.
  • Because the minimum-order claim rests on the exhaustiveness of the 46- and 50-vertex dual lists, independent re-generation of those lists would either confirm the 29 threshold or expose a missed graph.
Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

  1. Claim #1: The central result is Theorem 2.5: the minimum order of a counterexample to the Albertson-Berman conjecture is $29$. The witness $G_{29}$ is built by identifying the distinguished edge $xy$ of a $14$-vertex gadget $Q$ with the distinguished edge $bc$ of a $17$-vertex gadget $R$, both mild modifications of the icosahedron. The key profile for $R$ is $(p_R(\emptyset),p_R(\{b\}),p_R(\{c\}),p_R(\{b,c\

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper studies the Albertson-Berman conjecture that every planar graph contains an induced forest of order at least half its vertices. The authors construct explicit 29-vertex counterexamples, prove via exhaustive computation that no counterexample has fewer than 29 vertices, construct infinitely many 4-connected 5-edge-connected counterexamples with a unique minimum order of 41, and give an infinite family of planar graphs with induced-forest ratio at most 25/52, which also disproves a conjecture of Chappell and Pelsmajer for every d≥7. The lower-bound part of the minimum-order theorem is reduced by Lemma 2.2 and Stein's theorem to checking all planar triangulations on 25 and 27 vertices whose duals are nonhamiltonian cubic planar 3-connected graphs on 46 and 50 vertices; this check is performed by a large enumeration reported as taking approximately 10 CPU years.

Significance. If the computational claims are accepted, the results are significant: they settle the minimum order of a counterexample to the Albertson-Berman conjecture, positively answer Jung's question on 4-connected planar counterexamples, and improve the best known upper bound on c_P from 15/31 to 25/52. The explicit constructions (G29, G41, G52) are self-contained, and the gadget values on which they rely are exact small computations that the authors also describe as verifiable by case analysis. The paper also makes the small graphs available at the House of Graphs. The main weakness is that the headline lower-bound theorems rest on exhaustive computations whose code, data, and certificates are not shipped, so the central claims are not independently reproducible as they stand.

major comments (4)
  1. [Section 2, Observation 2.4 and Theorem 2.5 (plantri enumeration paragraph)] The lower-bound half of Theorem 2.5 rests entirely on the claimed exhaustive enumeration of nonhamiltonian cubic planar 3-connected graphs on 46 and 50 vertices, summarized in Table 1. The manuscript reports generation counts and a 10 CPU-year computation but does not provide the generator scripts, the Hamiltonicity filter, the face-contraction and vertex-expansion recovery code, or the list of the 441,578 nonhamiltonian 50-vertex graphs. A missed graph in this enumeration would invalidate Observation 2.4 and hence Theorem 2.5. Please make the code and data available as supplementary material and describe an independent validation, for example by reproducing the counts of Holton-McKay and McKay for n≤48 and by cross-checking the Hamiltonicity filter on a sample with an independent solver.
  2. [Section 3, Theorems 3.1 and 3.2] The minimum-order and uniqueness statements for 4-connected 5-edge-connected counterexamples depend on the previously generated list from reference [11] and on new computations of the maximum induced forest order for all relevant duals, as well as on an exhaustive edge-deletion verification for Theorem 3.2. None of these computational artifacts are shipped. Please publish the exact lists used, the parameters of the generation, the version and configuration of the Iwata-Imanishi feedback vertex set solver, and the scripts for the edge-deletion check, so that the uniqueness and minimality claims can be independently verified.
  3. [Section 3, definition of the infinite family G_{41,k}] The construction of the infinite family G_{41,k} asserts without detailed proof that the replacement operation yields a planar triangulation without separating triangles and with minimum degree at least 5. These two properties are exactly what makes the family 4-connected and 5-edge-connected, so the assertion is load-bearing for the claim of infinitely many such counterexamples. Please provide a proof (or a machine-checkable certificate of the local replacement) that both properties are preserved at every step.
  4. [Section 4, Observation 4.3] Observation 4.3 states a universal lower bound of 25/52 for all 4-connected 5-edge-connected planar graphs on at most 41 vertices. This is a strong statement derived from the same unshipped computations as Theorems 3.1 and 3.2, and it inherits the reproducibility problem. It should be backed by the same released lists and scripts, or explicitly stated as conditional on those computations.
minor comments (4)
  1. [Section 2, p-value display] In the display of the p-values for Q and R, the empty set appears as "H" in the text; this should be typeset as \emptyset.
  2. [Section 2, paragraph after Figure 3] The claim that "up to isomorphism, there is a unique way to add one more edge to G29 that results in a planar triangulation" is stated without justification; either give a short argument or mark it explicitly as a finite check.
  3. [Section 3, paragraph on G_{41,k}] The equality "edge-connectivity of a planar triangulation equals its minimum degree" is cited to reference [21], which concerns simplicial polytopes; please make the transfer to arbitrary planar triangulations explicit.
  4. [References] Reference [18] is listed only as an arXiv preprint; update it if a journal version has appeared.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the extremal bounds follow from explicit constructions, external theorems, and independent exhaustive enumeration.

full rationale

All three main outputs (minimum order 29, minimum 4-connected 5-edge-connected order 41, and c_P <= 25/52) are established by explicit finite constructions (G29, G41, G52) combined with external theorems such as Stein's theorem and with exhaustive enumeration whose inputs are independently generated graph lists. No parameter is fitted to make a target value come out: the gadget values (6,7,7,7) and (8,8,8,9) are exact finite computations that the paper also says can be verified by short case analysis, and the 25/52 bound follows directly from the construction of G52 and the stated gadget invariant. The lower bound for Theorem 2.5 depends on the completeness of the generated nonhamiltonian cubic planar 3-connected graph lists, but that completeness is an input to the argument, not a reformulation of the conclusion; the Hamiltonicity filter and dual reformulation are justified by Stein's theorem and standard planar duality, not by the counterexample claim. The use of the authors' earlier graph lists [11] in Section 3 is a self-citation, but it supplies an independently generated structural database with parameter-free assumptions (girth, cyclic edge-connectivity, order bounds) that do not include the target result; it therefore counts as real computational evidence rather than a circular premise. The 10 CPU-year enumeration and FVS computations are not shipped as code or certificates, but that is a reproducibility and completeness risk, not a circularity: no equation in the paper defines the answer into its computational input. Accordingly, no circular step is identified.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No numbers are fitted to data; all constructions are explicit and all induced-forest values are exact, so the ledger contains no free parameters. The finite graph gadgets Q and R are explicit and verifiable constructions, not unexplained postulated entities.

assumptions (6)
  • standard math Stein's theorem (Theorem 2.3): a planar triangulation can be partitioned into two induced forests if and only if its dual is Hamiltonian.
    Invoked in Section 2 to restrict the search for small counterexamples to triangulations with nonhamiltonian duals.
  • domain assumption Contracting a triangular face of a nonhamiltonian cubic planar 3-connected graph yields a smaller nonhamiltonian cubic planar 3-connected graph, and the process reverses by expanding a vertex into a triangle.
    Used in Section 2 to recover all graphs with faces of size 3 from the triangle-free list; stated without proof.
  • ad hoc to paper plantri exhaustively generates every cubic planar 3-connected graph without faces of size 3 on n vertices, and the Hamiltonicity filter is exact.
    The min-order theorem relies on the completeness of this 10 CPU-year enumeration of 16,747,182,732,792 graphs on 50 vertices.
  • ad hoc to paper The Iwata-Imanishi feedback vertex set solver computes exact values for all tested graphs.
    ap(G) is computed as |V(G)| minus feedback vertex set number in Observation 2.4 and Theorems 3.1 to 3.2; no certificates are provided.
  • ad hoc to paper The previously generated list of all cyclically 4-edge-connected cubic planar 3-connected graphs of girth at least 5 on at most 78 vertices from reference [11] is complete.
    Used in Section 3 to prove uniqueness of the minimum 4-connected 5-edge-connected counterexample G41.
  • standard math The edge-connectivity of a planar triangulation equals its minimum degree (Pilaud et al., reference [21]).
    Used in Section 3 to infer 5-edge-connectivity of the constructed triangulations G41,k.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound." pith.science (2026). https://pith.science/paper/FIUWBXDE

@misc{pith2026260823260,
  author       = {Pith},
  title        = {Pith review of: Counterexamples to the Albertson-Berman conjecture: minimum order, connectivity and an improved ratio bound},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FIUWBXDE}},
  note         = {Machine review of arXiv:2608.23260}
}
abstract

In 1979, Albertson and Berman conjectured that every planar graph $G$ contains an induced forest of order at least $|V(G)|/2$. This long-standing conjecture was recently disproved by several explicit counterexamples, which naturally led to several extremal and structural questions that we answer. We combine mathematical arguments and exhaustive computations to show that the minimum order of a counterexample is $29$. We also construct infinitely many $4$-connected $5$-edge-connected counterexamples (and show that the unique such counterexample of minimum order has order $41$), whereas previously all known counterexamples had vertex-connectivity at most $3$. Furthermore, we construct an infinite family of planar graphs on $n$ vertices whose maximum induced forests have order at most $\frac{25}{52}n$, thereby improving the previous best upper bound. This family also yields infinitely many counterexamples (for every integer $d \geq 7$) to a conjecture of Chappell and Pelsmajer concerning induced forests of maximum degree at most $d$.

Figures

Figures reproduced from arXiv: 2608.23260 by the authors.

Figure 1
Figure 1. The 14-vertex gadget Q. The distinguished edge is xy. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. The 17-vertex gadget R. The distinguished edge is bc. For a graph J P tQ, Ru with distinguished edge uv and X Ď tu, vu, we define pJ pXq :“ max␣ |F| : F Ď V pJq, JrFs is a forest and F X tu, vu “ X ( . We computationally verified that ` pQpHq, pQptxuq, pQptyuq, pQptx, yuq˘ “ p6, 7, 7, 7q and ` pRpHq, pRptbuq, pRptcuq, pRptb, cuq˘ “ p8, 8, 8, 9q. These values are not essentially computational: using the descriptions … view at source ↗
Figure 3
Figure 3. The 29-vertex graph G29 obtained by identifying xy in Q and bc in R. Adding the dashed edge to G29 results in G1 29. Theorem 2.5. The minimum order of a counterexample to the Albertson-Berman conjecture is 29. We now recall standard terminology that we will use in the next section. A graph with at least k ` 1 vertices is k-connected if deleting any set of fewer than k vertices leaves a connected graph. The vertex co… view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: The unique smallest 4-connected 5-edge-connected planar graph G41 that is a counterexample to Conjecture 1.1. It has 41 vertices. The blue vertices together with the two yellow vertices induce a copy of Q´xy, the green vertices together with the two yellow vertices ind…
Figure 5
Figure 5. Figure 5: The 52-vertex graph G52. The bold edges indicate edges that are not present in one of the three copies of R. without a separating triangle and with minimum degree at least 5 (therefore G41,k is 4-connected and 5-edge-connected, since the edge-connectivity of a planar t…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [11]

    Goedgebeur and C.T

    J. Goedgebeur and C.T. Zamfirescu. Improved bounds for hypohamiltonian graphs.Ars Math. Contemp.13(2017) 235–257

    work page 2017

  2. [1]

    M. O. Albertson and D. M. Berman. A conjecture on planar graphs. In J. A. Bondy and U. S. R. Murty (eds.),Graph Theory and Related Topics, Academic Press, New York, 1979, p. 357

    work page 1979

  3. [2]

    N. Alon, D. Mubayi and R. Thomas. Large induced forests in sparse graphs.J. Graph Theory38 (2001) 113–123

    work page 2001

  4. [3]

    Fractional vertex-arboricity of planar graphs

    M. Bonamy, F. Kardoš, T. Kelly and L. Postle. Fractional vertex-arboricity of planar graphs. arXiv preprint arXiv:2009.12189(2020)

    work page Pith review arXiv 2020

  5. [4]

    O. V. Borodin. On acyclic colorings of planar graphs.Discrete Math.25(1979) 211–236

    work page 1979

  6. [5]

    O. V. Borodin and A. N. Glebov. On the partition of a planar graph of girth5into an empty and an acyclic subgraph.Diskretn. Anal. Issled. Oper. Ser. 18(2001) 34–53

    work page 2001

  7. [6]

    Bradshaw, T

    P. Bradshaw, T. Masařík, J. Novotná and L. Stacho. Robust connectivity of graphs on surfaces. SIAM J. Discrete Math.36(2022) 1416–1435

    work page 2022

  8. [7]

    Brinkmann and B.D

    G. Brinkmann and B.D. McKay. Fast generation of planar graphs.MATCH Commun. Math. Comput. Chem.58(2007) 323–357

    work page 2007

Show all 23 references
  1. [8]

    G. G. Chappell and M. J. Pelsmajer. Maximum induced forests in graphs of bounded treewidth. Electron. J. Combin.20(2013), no. 4, #P8

    2013

  2. [9]

    Coolsaet, S

    K. Coolsaet, S. D’hondt and J. Goedgebeur. House of Graphs 2.0: A database of interesting graphs and more,Discr. Appl. Math.325, (2023), 97–107. Available athttps://houseofgraphs.org

    2023

  3. [10]

    D. W. Cranston and L. Rabern. Planar graphs have independence ratio at least3{13.Electron. J. Combin.23(2016), no. 3, #P3.45

    2016

  4. [12]

    D. A. Holton and B. D. McKay. The smallest non-hamiltonian3-connected cubic planar graphs have38vertices.J. Combin. Theory Ser. B45(1988) 305–319

    1988

  5. [13]

    Y. Iwata. Linear-Time Kernelization for Feedback Vertex Set.Proc. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs)80(2017) 68:1-68:14

    2017

  6. [14]

    Iwata and K

    Y. Iwata and K. Imanishi. Source code of feedback vertex set solver [Computer software].GitHub repository.Available athttps://github.com/wata-orz/fvs

  7. [15]

    H. Jung. A15{31counterexample family to the Albertson–Berman conjecture.arXiv preprint arXiv:2608.17350(2026)

    2026 arXiv

  8. [16]

    Kawarabayashi and C

    K. Kawarabayashi and C. Thomassen. Decomposing a planar graph of girth5into an independent set and a forest.J. Combin. Theory Ser. B99(2009) 674–684

    2009

  9. [17]

    34(2018) 1217–1246

    H.Le.Abetterboundonthelargestinducedforestsintriangle-freeplanargraphs.Graphs Combin. 34(2018) 1217–1246

    2018

  10. [18]

    M. Makarov. A counterexample to the Albertson–Berman conjecture about induced forests in planar graphs.arXiv preprint arXiv:2608.13964(2026). 10

    2026 arXiv

  11. [19]

    B. D. McKay. Combinatorial data: plane graphs. Available athttps://users.cecs.anu.edu.au/ ~bdm/data/planegraphs.html

  12. [20]

    B. Mohar. Induced forests in planar graphs.Problem of the Month, July 2002. Available athttps: //www.sfu.ca/~mohar/Problems/P0208InducedForestPlanar.html

    2002

  13. [21]

    Pilaud, G

    V. Pilaud, G. Pineda-Villavicencio and J. Ugon. Edge connectivity of simplicial polytopes.Euro- pean J. Combin.113(2023), 103752

    2023

  14. [22]

    S. K. Stein.B-sets and planar maps.Pacific J. Math.37(1971) 217–224

    1971

  15. [23]

    D. B. West. Induced forests in planar graphs.Problems in Graph Theory and Combinatorics. Available athttps://dwest.web.illinois.edu/openp/planforest.html. 11

Pith tools

Reviewed August 28, 2026 · model on record in the stance chip above.