Literature check

What Lean checks

Lean proves arbitrary vertex decomposability for tripods with a positive short arm of length at most two, conditional on source tests 1 and 5. For all positive short-arm lengths it proves partitions containing a larger part under those tests, realizes partitions with a sublist summing to the short arm unconditionally, and reduces the remainder to partitions with no mergeable noncentral pair. The general all-small case, four-arm reduction, existence constructions and combined gate remain. Strict compilation, a 958-theorem full-chain axiom audit and isolated kernel replay passed.

Checked November 20, 2026. The target is Conjectures 1 and 2 in §4 of the 2006 preprint On arbitrarily vertex decomposable trees, published in Discrete Mathematics 308 (2008), 1268–1281. Both concern the sufficiency of arithmetic conditions for arbitrary connected vertex partitions. The authors prove sufficiency under a quadratic lower bound on the second regular arm in Theorem 19, and separately check a smaller admissible example. The proof in this repository removes that bound in both conjectures. Original preprint · Journal DOI

Closest results checked

Source Scope
Barth, Baudon and Puech (2002) Polynomial algorithm for tripods and the reduction to two consecutive sizes with a possible smaller part. Horňák and Woźniak state this reduction as Theorem 9.
Barth and Fournier (2006), §4 Maximum degree at most four, a leaf adjacent to each degree-four vertex, and a polynomial algorithm for multipodes. Lemma 10 yields the reduction used in Theorem 10.
Horňák, Tuza and Woźniak (2007), §4 Online decomposability and short-arm results for the ordinary problem.
Barth, Fournier and Ravaux (2009), Theorem 7 Constructions of arbitrarily long-arm decomposable combs, including the relevant tripod shapes. This addresses existence rather than sufficiency of the five tests.
Horňák, Marczyk and Woźniak (2010), Questions 22.1–22.2 States existence at every prescribed shortest regular arm as open in both classes. The explicit construction answers these questions.
Juszczyk and Zioło (2010), §§1–2 Restates the partition reductions and characterizes the particular families S(2,3,b,c)S(2,3,b,c) and S(4,b,c)S(4,b,c) in its notation.
Ravaux (2010) Decomposability criteria and an algorithm for trees of large diameter.
Liu, Wu and Meng (2020) Characterization for a class of forbidden-subgraph graphs and references to the literature on decomposable trees.
Tang, Wang and Wang (2026) Chromatic symmetric functions of caterpillars. The earlier decomposability theorem supplies context for the classification.
Baudon, Bensmail and Vayssieres (2026) Connected partition problems that allow additional vertices to support connectivity.

I checked citation lists for the work in OpenAlex and Semantic Scholar, screened titles and abstracts for later spider or star-like tree classification, and followed the relevant references above. I also searched the article title, the authors' names with and without diacritics, the two numbered conjectures, and combinations of “admissible sequence,” “star-like tree,” “spider,” “tripode,” “arbitrarily partitionable,” and “arbitrarily vertex decomposable.” The 2006 maximum-degree result also resolves an earlier conjecture of these authors, so searches by names alone often return that result. The source audit found no earlier proof or disproof of the two §4 conjectures in their full stated ranges. Priority remains open to corrections from the wider literature.