经典证明：为什么n=5时不存在Leech树？

在一棵树中，任意两个顶点之间的路径都是唯一的。如果一棵树有 n 个顶点，那么这棵树总共会有 n(n-1)/2 条路径（每两个顶点都会确定出一条路径来）。 1975 年， John Leech 提出了这么一个问题：有多少顶点数为 n 且边上带权的树，使得图中所有 n(n-1)/2 条路径的权值之和正好是 1, 2, …, n(n-1)/2 ？Leech 本人给出了五个这样的例子，其中四个如下图所示，顶点数 n 分别为 2 、 3 、 4 、 4 。第五棵满足要求的树拥有 6 个顶点，把它找出来将会是一个不小的挑战，感兴趣的读者不妨尝试一下，本文最后会公布答案。 Leech 注意到了 n = 5 时是无解的，但却并没有给出一个解释。

1977 年， Herbert Taylor 给出了一个非常漂亮的解释：如果一棵树满足上述要求，那么顶点数 n 一定是形如 m²或者 m²+ 2 的数。让我们来看一看这个精妙的证明。

给定一棵树后，首先按照下述原则对所有顶点进行红蓝二染色：如果某条边的权值为偶数，则两端的顶点同色；如果某条边的权值为奇数，则两端的顶点异色。这是总能办到的，比如我们可以先随便选一个顶点，把它染成红色，然后从这个顶点出发，按照规则一点一点地推出其他顶点的颜色。由于整个图是一棵树，图中没有回路，因此往外推理的过程中不会走回已经染过色的地方，因而不会有矛盾产生。如果用 r 来表示所有红色顶点的数目，用 b 来表示所有蓝色顶点的数目，则 r + b = n 。

注意到，如果一条路径的权值之和为奇数，就说明这条路中有奇数条权值为奇数的边，也就说明沿着这条路径行走的过程中，顶点的颜色改变了奇数次。因此，两个顶点之间的路径权值之和为奇数，当且仅当这两个顶点是异色的。这说明，权值之和为奇数的路径一共有 rb 条。

如果所有 n(n-1)/2 条路径的权值之和依次是 1, 2, …, n(n-1)/2 ，那么当 n(n-1)/2 是偶数的时候，权值之和为奇数的路径应该有 (n(n-1)/2)/2 条；当 n(n-1)/2 是奇数的时候，权值之和为奇数的路径应该有 (n(n-1)/2 + 1)/2 条。

在前一种情况中， rb = (n(n-1)/2)/2 ，即 4rb = n(n-1) 。于是：

n = n²– 4rb

= (r + b)²– 4rb

= r²+ b²+ 2rb – 4rb

= r²+ b²– 2rb

= (r – b)²

在后一种情况中， rb = (n(n-1)/2 + 1)/2 ，即 2 · (2rb – 1) = n(n-1)。于是：

n = n²– 4rb + 2

= (r + b)²– 4rb + 2

= r²+ b²+ 2rb – 4rb + 2

= r²+ b²– 2rb + 2

= (r – b)²+ 2

由于数字 5 既不是一个平方数，也不具有平方数加 2 的形式，因而 n = 5 是无解的。下图则是 Leech 找到的那个 n = 6 时的解：

有趣的是，目前除了 Leech 本人找到的这五个解以外，还没有人找到任何新的解。人们猜想 Leech 树的数目是有限的，但目前还没有人证明这一点。

参考资料：http://www.cut-the-knot.org/arithmetic/combinatorics/LeechTrees.shtml