OEIS A007187 · Guy §C10 · tree labelling
Draw a tree: dots joined by lines, no loops. Write a whole number on each line. Now, for every pair of dots, add up the numbers along the path between them. With eleven dots there are fifty-five pairs, so you get fifty-five totals.
How many of the numbers 1, 2, 3, … can you force to appear among those totals? If you could get all fifty-five, 1 through 55, the tree would be perfect, and for eleven dots that is known to be impossible. So how close can you come?
John Leech asked this in 1975 and worked it out up to ten dots. The eleven-dot answer has sat in the sequence database ever since as "at least 48", with nobody named for it. It is 49. The tree below reaches it, and an exhaustive search shows no eleven-dot tree reaches 50.
Click any number on the line beneath the tree and the path that produces it lights up. Six numbers come out twice, which is exactly the slack the tree cannot avoid.
Everything below is the technical version. The caveat that matters: the refutations at 11 and 12 vertices come from one search program, checked against the published table and against two other engines at smaller sizes, not from two independent programs at that size.
For a tree T on n vertices with positive integer edge weights, say T covers [1, k] when every integer 1, …, k is the weighted length of some path. Leech (1975) asked for the largest such k, written a(n), and computed a(2..10) = 1, 3, 6, 9, 15, 20, 26, 34, 41; the OEIS entry A007187 has since carried only a(11) ≥ 48 and a(12) ≥ 55.
This note gives a budgeted form of the forced-least-missing-weight recursion, proves the six pruning lemmas it relies on, re-derives a(2..10) from scratch, and determines a(11) = 49 certified: an explicit tree covers [1, 49], and an exhaustive search over 1.40·10⁹ nodes shows that no tree on 11 vertices covers [1, 50]. It also establishes 57 ≤ a(12) ≤ 60 certified, and computes the distinct-sum analogue, the maximum Leech index of Varghese, Lakshmanan and Arumugam, as 1, 3, 6, 9, 15, 20, 25, 30, 37, 45, 47 for n = 2, …, 12, a sequence not in OEIS.
The refutations at n = 11 and 12 are exhaustive searches by a single engine, with node counts recorded and reproducible; they are not proofs in the sense of a written argument, and the page says so wherever the numbers appear.
Let T = (V, E, w) be a tree with n vertices and positive integer weights, d(x, y) the weight of the unique path between x and y, and N = C(n, 2). The multiset of all d(x, y) is the distance spectrum. T covers [1, k] when every value 1 to k appears in it, and a(n) is the largest k achievable on n vertices.
Trivially a(n) ≤ N, with equality exactly when a Leech tree exists, one whose spectrum is precisely [1, N]. Taylor (1977) showed this forces n = m² or m² + 2, and the orders 5, 9, 11, 16 and 18 have been excluded, so below 25 vertices only n = 2, 3, 4 and 6 have Leech trees. All of this is cited here through Ghodsi (arXiv:2609.20492); the original papers are paywalled and were not read.
If T covers [1, k] then exactly k of its N pairs are first realisations of the values 1 to k and the other E = N − k pairs are excess: they repeat a value already seen or exceed k. Excess is the quantity the search budgets, and the excess sequence N − a(n) for n = 2 to 11 is 0, 0, 0, 1, 0, 1, 2, 2, 4, 6. The eleven-vertex optimum wastes six of its fifty-five pairs.
Fix n, k and the budget B = N − k. Order the edges of a covering tree by nondecreasing weight and let Fj be the forest of the first j. Write mj for the least value of [1, k] not realised inside a component of Fj. The engine enumerates the chains F0 ⊂ F1 ⊂ … , choosing at each step a weight, two components and a port in each. Each lemma below is a statement about an arbitrary covering tree, so nothing the search skips can be a solution.
All six are proved in the note in the repository. Together they turn a search that would be hopeless into one that finishes n = 11 in under five minutes on four cores.
a(11) = 49. The tree (0,1,1) (2,3,1) (0,4,2) (5,6,4) (3,6,5) (5,7,7) (6,8,8) (5,9,11) (2,10,22) (0,3,24) has distance multiset [1..49] together with a second copy of 1, 11, 23, 25, 26 and 39. No tree on 11 vertices covers [1, 50].
The witness was checked by a program written from the definition, and again independently on 20 September 2026 for this page: 55 path sums, every value 1 to 49 present, six values twice, nothing above 49. Three further witnesses, one from each of the other workers, are in the run records and were checked too; they are not claimed to be inequivalent.
The upper bound is the exhaustive search, split into four worker prefixes at depth 5:
| k | budget B | workers | nodes | verdict |
|---|---|---|---|---|
| 55 | 0 | 1 | 2,434,374 | no tree (no Leech tree of order 11, as known) |
| 54 | 1 | 1 | 26,512,620 | no tree |
| 53 | 2 | 1 | 27,939,234 | no tree |
| 52 | 3 | 1 | 121,430,938 | no tree |
| 51 | 4 | 2 | 493,075,490 | no tree |
| 50 | 5 | 4 | 1,400,728,816 | no tree |
| 49 | 6 | 4 | 85,450,603 to the first witness | witness |
| 48 | 7 | 1 | 1,376,421 to the first witness | witness, reproducing the recorded bound |
57 ≤ a(12) ≤ 60. The lower bound is the 12-vertex tree in the figure above, which covers [1, 57] with nine excess pairs, where OEIS recorded a(12) ≥ 55. The upper bound refutes k = 61 over 16,081,755,104 nodes on three workers, and k = 62 separately over 4,863,094,430.
Witness hunts at k = 58 and 59 ran 30 and 25 minutes and found nothing, which is not evidence of nonexistence and is not offered as any. Deciding a(12) means refuting budget 8, and the growth in the figure above says that is around 1011 nodes.
If all path sums are required to be distinct, the maximum over trees of order n, the maximum Leech index of Varghese, Lakshmanan and Arumugam, is 1, 3, 6, 9, 15, 20, 25, 30, 37, 45, 47 for n = 2, …, 12. It agrees with a(n) up to n = 7 and falls behind from n = 8 on. The sequence is not in OEIS.
| n | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| a(n), repeats allowed | 1 | 3 | 6 | 9 | 15 | 20 | 26 | 34 | 41 | 49 | 57 to 60 |
| distinct sums | 1 | 3 | 6 | 9 | 15 | 20 | 25 | 30 | 37 | 45 | 47 |
| C(n,2) | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 | 66 |
Every value of the distinct-sum row is reproduced by a deliberately minimal second engine, which uses the weight window and the budget and nothing else, and the witnesses were re-checked here: the 11-vertex one realises 1 to 45 and ten larger values, all fifty-five sums distinct; the 12-vertex one realises 1 to 47 and nineteen larger values.
The engine re-derives the whole published ladder from scratch in under 15 seconds for n ≤ 10, witnesses and refutations alike, and all nine values agree with A007187. An independent SAT engine, one CNF per unlabelled tree shape with unary weights, agrees at n = 7 and 8 on both verdicts and at n = 9 on k = 35, where all 47 shapes are unsatisfiable, 84 minutes of one core in total. A deliberately minimal second search engine reproduces every value it was run on, and refutes the repeat-allowed k = 42 at n = 10 in 43,182,621 nodes, which makes a(10) = 41 two-engine on both sides. For n ≤ 7 both variants were also confirmed by brute force over every tree shape and weight vector.
What is not two-engine is the pair of refutations that matter most: k = 50 at n = 11 and k = 61 at n = 12. Those rest on one C program, whose soundness rests on the six lemmas and on its exact agreement with the published ladder, with a variant of itself that generates children by brute force rather than from candidate lists (identical node counts), and with the SAT engine where that was run. A second, independently written engine at n = 11 is the obvious next step, and until it exists a(11) = 49 is certified, not proved.