# Leech Trees and Taylor's Criterion<

A tree is a connected graph with no cycles. A weighted graph (or, more accurately, and *edge-weighted* graph) has each of its edges associated with a number - its weight. A path on a weighted graph is also assigned weight, which is the sum of the weights of the edges that compose the path.

A tree with $N$ vertices (or nodes) has $N-1$ edges, and since in a tree there is always a unique path between two vertices, and the total number of paths equals $N(N-1)/2$.

In a short 1975 article J. Leech posed a problem where he asked for the existence of trees with $N$ vertices and edges so labeled that the $N(N-1)/2$ paths in the tree all have different weights $1,2,3,\ldots,N(N-1)/2.$ He gave five examples. (Leech identified edge labeling with "length" and not "weight", which is reflected in the drawings below.)

No other examples have been found since. In 2005, L. Székely *et al* proved asymptotic estimates on the degree of vertices and the length of paths in trees with the Leech labeling (*Leech trees*) and conjectured that the number of Leech trees is finite. Other than that the only available results are negative. Leech himself established a non-existence of the labeling for $N=5,$ while checked computationally that there are no Leech trees with $9$ and $11$ vertices. A most remarkable result is due to H. Taylor:

An edge-labeled tree on $N$ nodes cannot have the consecutive path sums $1,\ldots,N(N-1)/2$ unless, for some integer $m$, $N = m^2$ or $N = m^{2} + 2.$

The beautiful proof has been reproduced by L. Székely *et al* and Ross Honsberger in his *Mathematical Gems III* collection. Here it is.

### Proof of Taylor's Criterion

We are going to label the vertices in two colors, say white and black. Starting with an arbitrary vertex and giving it either color, proceed along the unique paths to other vertices, assigning colors along the way in the following manner:

The color at the end vertex of an edge is the same as that of the starting vertex if the edge bears an even weight; the color is reversed for an odd edge.

Let $W$ and $B$ be the number of white and black vertices: $W+B=N.$ The key observation concerns the number $O$ of odd paths. Indeed, $O=W\cdot B.$ This is because the odd paths start and end at vertices of different colors. This can easily be shown by induction, or with Taylor's original argument:

Indeed, the unique path between two nodes will have an odd sum if and only if it makes an odd number of color changes. Thus any path sum will be odd if and only if the path has a black node at one end and a white node at the other end.

Since the required path lengths are the consecutive $1,2,\ldots,N(N-1)/2,$ there are as many odd as even paths, if $N(N-1)/2$ is even, and an extra odd path if $N(N-1)/2$ is odd. In the former case, $2WB=N(N-1)/2$ and in the latter $2WB=N(N-1)/2+1.$

Thus, if $N(N-1)/2$ is odd,

$N = N^2 - 4WB = (W+B)^{2}-4WB=(W-B)^2.$

In case $N(N-1)/2$ is odd,

$N = N^2 - 4WB + 2 = (W+B)^{2}-4WB + 2 =(W-B)^2 + 2.$

### References

- R. Honsberger,
*Mathematical Gems III*, MAA, 1985, pp. 56-60 - J. Leech,
__Another Tree Labeling Problem__,*Amer. Math. Monthly*82, 923-925, 1975 - L. Székely
*et al*,__Some non-existence results on Leech trees__,*Bull. Inst. Combin. Appl.*44, 37-45, 2005 - H. Taylor,
__Odd Path Sums in an Edge-Labeled Tree__,*Math. Mag.*50, 258-259, 1977

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny