Product of transpositions from edges of a tree is a cycle of length $n$ 
Consider a tree with $n$ vertices, labeled $1,2,\dots,n$ so that no label is used twice. We perform the following operation: each time, we pick an edge that hasn't been picked before and swap the labels of its endpoints. After performing this operation $n-1$ times, we get another tree with its labeling a permutation of the first graph's labeling.
Prove that this permutation is a cycle of length $n$.

A trivial result: this permutation cannot have fixed points, since if it did, our graph would need to have a cycle, which cannot happen.
I also have a flawed induction proof. We can remove a leaf of a tree, apply the induction hypothesis, then add the leaf back to prove the result. However, this only works if we pick the edge corresponding to the leaf last. I feel though that this induction argument can be modified to work.
 A: Let $T$ be a labeled tree and suppose that the induced permutation on $\{1,\dots, n\}$ is $\sigma(T)$. We want to show that $\sigma(T)$ is an $n$-cycle. Let $e$ be the last edge chosen in your algorithm, and let $T'=T/e$ the contraction of $e$ from $T$. Suppose that the vertices incident with $e$ in $T$ are $i$ and $j$. After the contraction, combine vertices $i$ and $j$ in $T$ into vertex $i$ in $T'$. 
By the inductive hypothesis, $\sigma(T')$ is a cycle of length $n-1$ on the set $\{1,\dots,\hat{j},\dots,n\}=\{1,\dots, n\} \setminus \{j\}.$ Then the permutation $\sigma(T)$ is obtained from the permutation $\sigma(T')$ by multiplication by the transposition $(i\;j)$. If we consider $\sigma(T')$ as a permutation of $\{1,\dots, n\}$, then it fixes $j$. Hence
$$\sigma(T) = \sigma(T') (i \; j)$$
is an $n$-cycle.
Of course this is basically your argument, but uses contraction to get rid of the last edge rather than assuming the last edge is incident to a leaf.
A: Your flawed induction proof can be salvaged. Let your edges be $e_1, e_2, \ldots, e_{n-1}$, and the corresponding transpositions be $t_1, t_2, \ldots, t_{n-1}$. Let $e_k$ be an edge containing a leaf. (Such an edge exists, since a leaf exists, as long as $n \geq 2$.) Then, you want to prove that $t_1 t_2 \cdots t_{n-1}$ is an $n$-cycle, but your argument shows that $t_{k+1} t_{k+2} \cdots t_{n-1} t_1 t_2 \cdots t_k$ is an $n$-cycle. However, $t_{k+1} t_{k+2} \cdots t_{n-1} t_1 t_2 \cdots t_k$ is conjugate to $t_1 t_2 \cdots t_{n-1}$ (in fact, we have $t_{k+1} t_{k+2} \cdots t_{n-1} t_1 t_2 \cdots t_k = q \left(t_1 t_2 \cdots t_{n-1}\right) q^{-1}$ for $q = t_{k+1} t_{k+2} \cdots t_{n-1}$), and it is clear that any permutation conjugate to an $n$-cycle is an $n$-cycle, so you get the desired conclusion.
