Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.