4
$\begingroup$

I need to find the number of undirected trees on $n$ vertices such that the edges (and not the vertices) are labeled and exactly one label appears twice (i.e. there are $n-2$ possible labels and they all appear).

My reasoning goes like this: From Cayley's formula we know there are $n^{n-2}$ trees with labeled vertices. Erase the label $n$ from its vertex and for every other vertex, move the label from the vertex itself to the edge in the direction of the $n$ vertex. This way we get a tree with $n-1$ labels for the edges. However, this argument is flawed, since for example 0--1--2 and 0--2--1 give the same labeled tree.

Now assume that I managed to fix the problem and find the number of edge-labeled trees with $n-1$ edges, and let's denote it by $k$; my next idea is choosing one of the $n-2$ first labels and relabeling $n-1$ to what I choose. This causes double-counting so I think I need to divide by 2 here, but nothing more. Hence the final number is $(n-2)k/2$. Am I correct in this reasoning - and how can I find k? Quite obviously it's not $n^{n-2}$ since otherwise $(n-2)k/2$ might not even be an integer (if $n$ is odd).

2 Answers 2

2

The correspondence between edge- and vertex-labellings may work better starting from the degree 1 vertices instead of edge $n$ which would be at a random location inside the tree. For the degree 1 vertices we have a unique choice of label to assign. Remove these vertices and edges and repeat the process until the tree is a single vertex (0 edges) or a single edge. These cases correspond to enumeration of trees on labelled vertices, with the "center" of the tree being a vertex or an edge, respectively.

2

This is an extended comment on the suggested approach, not an actual answer.

Let $T$ be a vertex-labelled tree on the vertex set $[n]=[1,n]\cap\mathbb{Z}^+$. As T.. suggested, label the edges by transferring labels from vertices of degree $1$ to their adjacent edges and working ‘inward’ until either

$\qquad$(a) all edges have been labelled, and exactly one vertex retains a label, or
$\qquad$(b) all but one edge, $e=\{j,k\}$, have been labelled and its endpoints retain their labels.

If case (b) occurs, let $m=\min([n]\setminus\{j,k\})$, and give $e$ the label of whichever of $j$ and $k$ is closer to $m$ in $T$. Clearly $T$ can be reconstructed from the resulting edge-labelled tree $T'$.

One label in $[n]$, say $m$, is not used for any edge. Close up the gaps in the labelling by decreasing by $1$ each label in $T'$ that is bigger than $m$, and call the resulting edge-labelled tree $T^*$; the map $T\mapsto T^*$ is exactly $n$-to-$1$, so $n^{n-3}$ edge-labelled trees are possible at this stage.

Unfortunately, the modification of $T^*$ by picking one of the labels in $[n-2]$ and replacing $n-1$ with it is not $2$-to-$1$. Consider the linear graph with $3$ edges. The three non-isomorphic edge labellings are represented by the permutations $123$, $213$, and $132$. These generate the labellings $121$ and $122$, $211$ and $212$, and $112$ and $122$, of which $121$, $122$, $211$, and $212$ are pairwise non-isomorphic.

Let $t(n)$ be the desired number. Clearly $t(0)=t(1)=t(2)=0$ and $t(3)=1$. It’s not hard to verify that $t(4)=6$: there are four with underlying linear graph and two with underlying star graph. By brute-force enumeration I find that $t(5)=42$ and $t(6)=464$. (I do not guarantee those values!) Comparison of $t(4),t(5)$ and $t(6)$ with $4,25$, and $216$, the corresponding values of $n^{n-3}$, suggests that any relationship between $t(n)$ and $n^{n-3}$ is likely to be rather complicated; at this point I’d look for a different approach.