I would appreciate some help coming up with an expression for the number of spanning trees of an undirected graph with m labeled edges but m+1 unlabled vertices.
The answer is supposed to be ${m+1}^{m-2}$, but the best I came up with is ${m+1}^{m-1}$, with help from this discussion.
What I did was using the Cayley forumula for undirected labeled trees with m+1 vertices, choosing the m+1 as my root and from there I "moved" the number on each vetex onto the edge before it.
In this way I managed to have a tree with m labeled edges, as I looked for, but from the given answer I guess I missed some double counting which I'm not able to detect.
Number of undirected trees with unlabled vertices and labeled edges
cayley-graphscombinatoricstrees
Related Solutions
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.
Here's a way to find the number. It looks like it might not be the best (Sloane's A055315 has other formulas), but it works.
Let $n$ be the number of vertices and $e=n-1$ be the number of edges.
Claim: There is exactly one vertex of degree $3$, all others have degree $2$ or $1$. (Assume otherwise, and we violate the Handshaking Lemma, which stipulates the sum of degrees is $2e=2(n-1)$.)
So, the trees look like this:
If we delete the degree-$3$ vertex, we obtain three components. These three components only have vertices of degree $1$ and $2$, and so must be paths. Suppose the paths have $a$, $b$ and $c$ vertices. Then $a+b+c=n-1$ and $a,b,c$ are all positive integers. Conversely, given three paths of lengths $a \geq 1$, $b \geq 1$ and $c \geq 1$ and $a+b+c=n-1$, we can join their endpoints to a new vertex to create an $n$-vertex tree with exactly three $3$ leaves.
Let $a(n)$ be the number of partitions of $n-1$ into $3$ non-zero parts; this is equivalent to Sloane's A001399 which includes the formula $$a(n)=1+\left\lfloor\frac{(n-1)^2+6(n-1)}{12}\right\rfloor$$ among others.
Given an unlabeled tree, we can label the vertices in $n!$ (not necessarily distinct) ways. In this way, we generate $a(n)\ n!$ labeled trees.
In some cases (not many), there are symmetries which need to be accounted for. Because of symmetry, in this case
we count every labeling twice. This happens whenever $\{a,b,c\}$ have two parts of the same size.
And in this case
we count every labeling six times. This happens when $\{a,b,c\}$ has all three parts of the same size.
In these cases, we'll need to add a correction.
In the first case: we subtract $$\sum_{a \geq 1:n-1-a \text{ is even and } \geq 2} \tfrac{1}{2}n!=\frac{\lfloor (n-2)/2 \rfloor\ n!}{2}$$ since we have double-counted the $\frac{1}{2} n!$ graphs with $b=c=\tfrac{n-1-a}{2}$.
In the second case: if $n-1 \equiv 0 \pmod 3$, we first "uncorrect" the first correction, so we add back in $\tfrac{1}{2}n!$ and then subtract $\frac{5}{6}n!$ since we originally counted six times the $\frac{1}{6} n!$ graphs with $a=b=c$.
This gives $$\begin{cases} a(n)\ n!-\tfrac{\lfloor (n-2)/2 \rfloor\ n!}{2} & \text{if } n-1 \not\equiv 0 \pmod 3 \\ a(n)\ n!-\tfrac{\lfloor (n-2)/2 \rfloor\ n!}{2}+\tfrac{1}{2}n!-\tfrac{1}{6} n! & \text{if } n-1 \equiv 0 \pmod 3. \end{cases}$$ in agreement with Sloane's A055315.
Best Answer
Let $T$ be a tree with $m$ edges labelled $1$ through $m$ and $m+1$ vertices. Pick any vertex, and label it $0$. Root $T$ at $0$. Label each vertex of height $1$ with the label of the edge joining it to $0$. Label each vertex of height $2$ with the label of the unique edge joining it to a vertex of height $1$. Continue in this fashion until every vertex has been given the label of the edge joining it to its parent in the rooted tree.
Each pair $\langle T,v\rangle$ of an edge-labelled tree with $m$ edges labelled $1$ through $m$ and a vertex $v$ of $T$ gives rise in this way to a distinct vertex-labelled tree on $m+1$ vertices labelled $0$ through $m$. If we start with such a vertex-labelled tree and take the vertex $v$ with label $0$ as the root, we can transfer the label on each of the $m$ remaining vertices to the edge joining it to its parent to reverse the process to recover $\langle T,v\rangle$. This shows that if there are $t_m$ edge-labelled trees with $m$ edges labelled $1$ through $m$, then $t_m(m+1)=(m+1)^{m-1}$, and hence $t_m=(m+1)^{m-2}$.