Enumeration of Equicolourable Trees

ID
TR-2000-04
Authors
Nicholas Pippenger
Publishing date
February 22, 2000
Length
30 pages
Abstract
A tree, being a connected acyclic graph, can be bicoloured in two ways, which differ from each other by exchange of the colours. We shall say that a tree is equicolourable if these bicolourings assign the two colours to equal numbers of vertices. Labelled equicoloured trees have been enumerated several times in the literature, and from this result it is easy to enumerate labelled equicolourable trees. The result is that the probability that a randomly chosen n-vertex labelled tree is equicolourable is asymptotically just twice the probability that its vertices would be equicoloured if they were assigned colours by independent unbiased coin flips. Our goal in this paper is the enumeration of unlabelled equicolourable trees (that is, trees up to isomorphism), both exactly (in terms of generating functions) and asymptotically. We treat both the rooted and unrooted versions of this problem, and conclude that in either case the probability that a randomly chosen n-vertex unlabelled tree is equicolourable is asymptotically 1.40499... times as large as the probability that it would be equicoloured if its vertices were assigned colours by independent unbiased coin flips.