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.)

Leech Trees

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

  1. R. Honsberger, Mathematical Gems III, MAA, 1985, pp. 56-60
  2. J. Leech, Another Tree Labeling Problem, Amer. Math. Monthly 82, 923-925, 1975
  3. L. Székely et al, Some non-existence results on Leech trees, Bull. Inst. Combin. Appl. 44, 37-45, 2005
  4. H. Taylor, Odd Path Sums in an Edge-Labeled Tree, Math. Mag. 50, 258-259, 1977

Combinatorial Proofs

  1. Combinatorial Proofs.
  2. Lucas' Theorem.
  3. Ways To Count.
  4. Geometric Proof of Wilson's Theorem.
  5. Partitioning a Circle
  6. A Minesweeper Theorem
  7. Another Binomial Identity with Proofs
  8. Counting Fat Sets
  9. Counting Permutations with Fixed Points
  10. Pythagorean Triples via Fibonacci Numbers

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

Copyright © 1996-2017 Alexander Bogomolny

 62105168

Search by google: