Fabian Arevalo

OEIS A007187 · Guy §C10 · tree labelling

The eleventh term of Leech's tree-labelling problem

a(11) = 49, certified: a tree on eleven vertices whose path sums cover 1 to 49, and an exhaustive search over 1.40 billion nodes showing that none covers 1 to 50. The first new term of the sequence since Leech's 1975 table. Also 57 ≤ a(12) ≤ 60, and a distinct-sum sequence that is not in OEIS.
18 September 2026 · research session · witnesses and run records in the Matematica repository.

Start here — no maths required

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.

Tree
The witness. Ten weighted edges on eleven vertices. Every integer from 1 to 49 is the total along some path; the numbers in bold on the line occur twice. All fifty-five path sums are computed in your browser from the edge list, so the claim in the caption is checked as you read it. The 12-vertex tree below it is the best known there, and reaches 57 where the sequence database recorded 55.

What this note adds

  1. a(11) = 49. The first new term of the sequence since Leech's 1975 table. The lower bound is the tree above; the upper bound is an exhaustive search over 1,400,728,816 nodes that finds no eleven-vertex tree covering 1 to 50.
  2. 57 ≤ a(12) ≤ 60, where the database recorded only 55 from below. The upper bound refutes 61 over 16,081,755,104 nodes.
  3. A second sequence. Requiring all the path sums to be distinct gives 1, 3, 6, 9, 15, 20, 25, 30, 37, 45, 47 for 2 to 12 vertices, which is not in the database and departs from Leech's numbers from eight vertices on.
  4. Six pruning lemmas, proved, which is what makes eleven vertices reachable at all: the edge weights can be taken in nondecreasing order, the next one is never larger than the least value still missing, and the number of wasted pairs only grows.

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.

AbstractSummary of results

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.

Section 1The problem, and what "excess" means

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.

Section 2The six lemmas that make eleven reachable

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.

  1. Weight window. w(ej+1) ≤ mj, and weights are nondecreasing. If the next weight exceeded mj, the whole path realising mj would already lie inside Fj.
  2. Monotone excess. The excess of a subforest never decreases as edges are added, and is bounded by B throughout.
  3. Parity, after Taylor, in budgeted form. This alone refutes the top of the ladder at several orders, for instance k = N and k = N − 1 at n = 8 and 10, at the root.
  4. Edge load. A bound on how many pairs a single edge can serve.
  5. Whole-block exact cover, after Ghodsi. Budgeted.
  6. Isomorphic components are interchangeable.

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.

Section 3a(11) = 49

Theorem 1 · certified

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:

kbudget Bworkersnodesverdict
55012,434,374no tree (no Leech tree of order 11, as known)
541126,512,620no tree
532127,939,234no tree
5231121,430,938no tree
5142493,075,490no tree
50541,400,728,816no tree
496485,450,603 to the first witnesswitness
48711,376,421 to the first witnesswitness, reproducing the recorded bound
What each wasted pair costs. Nodes explored to refute k at 11 vertices, against the excess budget B = 55 − k. Every extra pair the search is allowed to waste multiplies the work by roughly four, which is what puts a(12) out of reach: deciding whether a(12) = 57 means refuting budget 8, projected at about 1011 nodes. Measured node counts, joined by a line; the dashed line is a fitted factor of four per unit of budget, a model, shown for comparison only.

Section 4Twelve vertices, and a second sequence

Theorem 3 · certified

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.

Theorem 2 · certified, two engines

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.

n23456789101112
a(n), repeats allowed136915202634414957 to 60
distinct sums136915202530374547
C(n,2)1361015212836455566

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.

Section 5Controls, and what is single-engine

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.

Section 6Open questions

  1. a(12). Refuting k = 58 decides it if the answer is 57; at roughly 1011 nodes that is a multi-day run, or a better lemma.
  2. An independent engine at n = 11, to turn the single-engine refutation into a two-engine one.
  3. Priority on the distinct-sum sequence. Whether Varghese, Lakshmanan and Arumugam, or Lakshmanan and Eldho, tabulated the maximum over all trees of small order could not be checked: both papers are paywalled and only the abstracts were read.
  4. Submit both sequences. A007187 can take a(11) = 49 and the improved a(12) ≥ 57; the distinct-sum sequence is new.