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