Theorem. Fix any integer . Let be a positive multiple of and set . The trees with arm lengths and , measured in edges, are both arbitrarily vertex decomposable.
This gives every prescribed shortest arm order for the tripod and every prescribed second-smallest arm order for the four-arm tree. These are Questions 22.1 and 22.2 in the 2010 problem collection of Horňák, Marczyk and Woźniak, and they imply affirmative answers to Problems 1 and 2 in §4 of the original Horňák–Woźniak paper. The 2010 collection records existence for infinitely many tripod arm orders from the earlier comb construction, along with the original finite tables. Choosing the least possible above gives both trees order by the prime number theorem, since . 2010 problems, pp. 26–27 · Original paper, §4 · Comb construction
Proof
By the admissibility theorem, it suffices to check tests 1, 2 and 5 for both trees. For any modulus , let be 0 or 1 according as the optional one-edge arm is absent or present. Let be the sum of the three regular-arm residues modulo plus , and let be the sum of their quotients. Thus the order of the tree is .
Tests 1 and 2 say that the sum of the two smallest regular-arm residues plus is less than . The case when all regular-arm residues vanish satisfies both tests directly. At both tests are automatic.
Test 5 at index only applies if and the two-size partition that uses at most parts of size exists. Its count of the smaller parts is , and its count of the larger parts is . Thus the partition exists exactly when . In this case the test requires an arm with residue and quotient modulo satisfying
The second inequality is equivalent to for that arm's length .
Moduli at most
Here has residue zero. Write . If , the residue of is zero, so tests 1 and 2 hold. When , the sum is , and the arm of length has residue and passes the test 5 inequalities. For the test has no trigger.
If , the residue of is . The two smaller residues sum to , so tests 1 and 2 hold. For test 5, the arm of length has residue . Its quotient is at least , since is a common multiple of the consecutive integers and hence .
Moduli above
Write with . The residue of is .
If , let be the residue of . The sum gives tests 1 and 2. Here and . If test 5 applies, implies , and . Thus the arm of length gives the test 5 inequalities.
Otherwise let be the residue of , which lies in . Now , giving tests 1 and 2. The quotients of are , respectively, and . If test 5 applies, then
so by integrality. For the arm of length , its residue gives and . All required tests hold, and so both trees are AVD.