According to the official Iranian booklet, they actually ask for the following: "Show that the final permutation of the labels is a complete cycle of $n$ letters".

Since a permutation is a product of cycles, saying it contains exactly one cycle is equivalent to saying it is a cycle of length $n$ (albeit in a less direct way).

This is a main step in the 1959 paper http://citeseerx.ist.psu.edu/showciting?cid=275102 of Dénes. The point is that when you multiply a permutation by a cycle (i, j), it merges the cycles containing i and j if they were in different cycles (and otherwise splits the cycle containing both of them into 2 cycles). The acyclicity of the tree condition is the same as the condition that each multiplication is a merge, not a split. (The main result of the Dénes paper is that the number of factorizations of the long cycle $(1,2,\ldots,n)$ as a product of $n-1$ transpositions (the minimal number) is $n^{n-2}$; this result was obtained 70 years earlier by Hurwitz in a very different context.)

Suppose that there is a non-complete cycle. Look at the first time that a there is a switch between a vertex in the cycle and a vertex not in the cycle. Remove the edge used in that switch, you now have two connected components, one of them should have more "cycle vertices" by the end of the permutation than it currently has. However there is going to be no more inter-component traffic for the remainder of the permutation, so this "cycle" is not a "cycle". Therefore the vertices of a cycle must satisfy that when doing the permutation there are no edges between a cycle vertex and a non-cycle vertex, but since each vertex is used this forces the cycle to be complete.

Proof by induction: For $n=2$ it's trivial. Suppose that for $n=k$ it's true. Consider a tree $G$ with $k+1$ vertices. Take a leaf $v$ labeled $i$ and the edge connected to it. WLOG assume $i=n+1$. Also let the label of the vertex connected to this edge right before it was picked as $j$. Now label the "label $n+1$" with $j$. (Put a second label on the first label.) In other words, just ignore the leaf $v$ from graph $G$ after label $j$ was put on it - because it wasn't used after that, all of the edges connected to it were picked, so ignoring it wouldn't change anything - and see label $n+1$ as it is label $j$, and continue picking edges. Now from tree $G/v$ pick the edges in the order I picked the edges from $G$ , and then we recieve one cycle. Now we look back at $j$ as $n+1$ , and bring back the former $j$. But we know that the real $j$ is finally at the place where $n+1$ was at first and $n+1$ is at place that $\sigma(j)$ was at first. But it's trivial that the rest of the permutation remains unchanged, so this new permutation just adds $n+1$ to the cycle of the old permutation. So at last we still have exactly one cycle, which was to be demonstrared.

thepurplelefant, I cannot make much sense of what you have written. What does "non-complete cycle" mean? What is "traffic"? TheOverlord, your solution appears to assume that the last step taken must connect a leaf to the rest of the tree. But this is not true. Consider for example the situation in which $n = 4$, the tree is the path with edges 12, 23, 34 and the order in which we choose the edges is to first choose 12, then 34, then the edge originally labeled 23 (but labeled 14 after the first two steps).

I think my post wasn't clear enough. I edited it.

JBL what I mean is suppose there is a cycle that doesn't contain all of the labels. Then look at the vertices which initially have the labels in that cycle, call those cycle vertices. Consider the first swap between a non-cycle label and a cycle label. that swap uses an edge. Look at the graph after deleting that edge, it is now two trees. But one of those trees just lost a cycle label, so it has less cycle labels that it had initially. If we want the cycle to indeed by a cycle vertex we need for the vertices which had cycle labels before the permutation to have cycle labels after. But this is impossible since that part of the subgraph lost a cycle label, and it cannot gain another cycle label, because the only link between the two trees is that edge, which has already been used up. Please comment if you think it makes sense.

thepurplelefant wrote: Please comment if you think it makes sense. It's a lot of words and could probably be polished for clarity, and also maybe would benefit from some good choice of notation. The main idea seems reasonable.

Hopefully this is not equivalent to what is said above or at least clarifies it. First of all I claim that no vertex can reach its initial position. If this were possible by swapping the vertex along distinct edges, then the tree would have to contain a cycle, which is impossible. For the rest of the proof the word "cycle" will refer to "permutation cycles" not graphs. Note that swapping the vertices for the first time creates a "cycle" of length $2$. Now I will prove that swapping vertices from different cycles causes the cycles to combine into one larger cycle. Suppose there is a vertex $a_i$ initially but label $a_{i+1}$ now and vertex $b_j$ which has label $b_{j+1}$ now. $a_i$ is part of a cycle $a_1,...,a_k$ and $b_j$ is part of a cycle $b_1,...,b_m$. After the swap, we have a new cycle $a_1,...,a_i,b_{j+1},...,b_j,a_{i+1},...a_1$ (this is also satisfied if $a_i=a_{i+1}$ or $b_j=b_{j+1}$). This cycle also works as long as $a_i\neq b_{j+1}, b_j\neq a_{i+1}$ which is implied by my first claim. Since we go through all $n-1$ edges of the tree, eventually every cycle will combine into a larger cycle.

No , it is not equivalent. Mabye this way can rephrase it. Suppose the permutation is not just one big cycle. Pick the vertices of one of the cycles and color them red. After the premutation all the red vertices will still be red. Consider the first time a red and a non-red vertex are swapped. Removing the edge used in the swap leaves two components. One of them has more red vertices than it had at the beginning, since the components are no longer connected at the end one of the components will have more red vertices than it had at the beginning. Therefore one vertex was red at the beginning and not at the end. Contradicting that the red vertices formed a cycle in the permutation.

Dear @TheOverlord and everyone, I have some stuck with problem, A permutation of a tree is still a tree with different lables, and how can it be a circle ? It is not clear enough. Dear @enescu, can you give me directed link to your booklet location? Iranian language is ok, and it will be very nice if it is English. And then, can you give me link to another booklet? I can only find 2017,2010-2013 booklet

Rather easy for an Iran TST problem. We use strong induction on $n$, with base case $n = 1$ trivial. Assume the result for all integers $k \leq n$, for some $n$. Suppose the first operation is performed on the edge that connects $a$ and $b$; remove the edge that connects them from $T$ (which is valid as we can never use this edge again). Then, $T$ is composed of two disjoint trees: $T_1$ and $T_2$. Obviously, any operation performed on an edge of $T_1$ does not affect $T_2$, and vice versa. We will now slightly alter the given process as follows. We will not swap the labels $a$ and $b$ yet; we will first perform the given operation on the edges of $T_1$ and $T_2$, and after this process is complete, we will swap the labels $a$ and $b$. In what follows, we will call this last swap the \textit{final swap}. Obviously this will leave the final permutation unchanged. By the inductive hypothesis, after each edge of $T_1$ has been operated on once, the labels of $T_1$ will be a permutation of length $|T_1|$ of the initial labels of $T_1$, and similarly for $T_2$. Now, we create a digraph on $\{1, 2, \ldots, n\}$ as follows: draw the edge $p \mapsto q$ iff $q$ now labels the vertex that was initially labelled by $p$. It suffices to show that this graph consists of a single directed cycle after all operations have been completed. We construct this graph after all operations other than the final swap have been performed. By the inductive hypothesis this graph is composed of two cycles; let them be $a \mapsto a_1 \mapsto a_2 \cdots \mapsto a_{|T_1|} = a$, and $b \mapsto b_1 \mapsto b_2 \cdots \mapsto b_{|T_2|} = b$. Now, swap the labels $a$ and $b$. The the edges of this graph will appear as follows: \begin{align*} a \mapsto b_1 \mapsto \cdots \mapsto b_{|T_2| - 1} \mapsto b \mapsto a_1 \mapsto \cdots \mapsto b_{|T_1| - 1} \mapsto a, \end{align*}which is a cycle of length $n$, as desired. This completes the inductive step, so we are done. $\Box$

We proceed with strong induction on the number of vertices . Base cases , being trivial are omitted. Delete the last used edge from the graph. This leaves us with two disjoint tree $T_1$ and $T_2$ . By the induction hypothesis, both $T_1$ and $T_2$ form cycles before the last edge is being operated on . Let the cycle associated with $T_1$ be $(i_1\mapsto i_2\mapsto \dots i_k\mapsto i_1)$ and the cycle associated with $T_2$ is $(j_1\mapsto j_2\mapsto \dots j_l\mapsto j_1)$ WLOG assume that the last edge is $\overline{i_2j_2}$ . Then after the last move, we have the new cycle (which essentially combines the previous two) $:=$ $$ (i_1\mapsto j_2\mapsto j_3 \mapsto \dots j_l \mapsto j_1 \mapsto i_2 \mapsto i_3 \mapsto \dots i_k \mapsto i_1)$$ We are done $\blacksquare$

Since we are trained in graph theoretic techniques, we induct by considering a leaf. Induct on $n$, the result is trivial for $n=1$. Let $u$ be a leaf. WLOG, $u$ is labelled with $n$. Let $\sigma$ denote the permutation formed by performing the operation $n-1$, then note that in each application of $\sigma$, we swap $u$ with some vertex $k$. WLOG, $k$ is the vertex originally labeled $1$. Finally, let the permutation $\sigma'$ on the remaining $n-1$ vertices, which we already know is a $n-1$-cycle, take $1\to 2,2\to 3,\dots$. Now, we observe that the resulting $\sigma$ must be $n-1\;n\;2\;3\;\cdots\;n-2\;1$, which is a $n$-cycle because $\sigma(1)=n-1,\sigma(n-1)=n-2,\cdots,\sigma(2)=n,\sigma(n)=1$.

Let $G_i$ be the directed graph associated with the permutation after $i$ turns, and let $T_i$ be subgraph of $T$ formed by the edges that have been used after $i$ turns. $\textbf{Claim: }$ If $a$ and $b$ belong to different cycles in $G_i,$ then switching $f(a)$ and $f(b)$ will "merge' the two cycles. At any given time, let $f(i)$ denote the number currently at the $i$th vertex of $T.$ $\emph{Proof: }$ Suppose the cycles are $aa_{1}a_{2}\dots a_{j}$ and $bb_{1}b_{2}\dots b_{k}.$ Then, $a\to b_1$ and $b\to a_1$ creates the cycle $ab_{1}b_{2}\dots b_{k}ba_{1}a_{2}\dots a_{j},$ which has length $j+k.$ $\blacksquare$ We claim that all switches must be as the above claim. Since $T$ is acyclic, it suffices to show the following. $\textbf{Claim: }$ If $x$ and $y$ belong to the same cycle of $G_i,$ then there is a path from $x$ to $y$ in $T_i.$ $\emph{Proof: }$ By induction, we may assume all previous turns merged cycles. Since $x$ and $y$ started in separate cycles, a cycle containing $x$ merged with a cycle containing $y$ at some point in the past. Now the claim follows from induction on cycle length. $\blacksquare$ Since all turns merge two cycles, there is exactly one cycle in $G_{n-1},$ as desired.

strong induckion. The base case $n=1$ is trivial. For the inductive step, suppose that we pick an arbitrary edge as our final edge; it connects two connected components each of size at most $n-1$, hence by the induckive hypothesis, before the final swap the permutation consisted of two disjoint cycles. The final swap would then join these two cycles.

I have a solution without induction, but based on a crucial observation. Look at the cycle decomposition of the permutation function at any stage. Suppose that the $k$ cycles have lengths $C_1,\cdots, C_k$ where we treat self-loops as a cycle of length 1. The main claim is then that the value $\sum_i(C_i-1)$ increases by exactly each move. Hence after $n-1$ moves, we arrive with \[n-1 = \sum_i(C_i-1) = \sum_iC_i-k = n-k\implies k = 1\]which is what we wanted. The proof of the claim is mainly to notice that each move merges two cycles, based on the tree condition and properties of transpositions.

I don't know if the actual permutation I wrote is correct or not... Induct on $n$, with base cases trivial. Suppose we add a leaf to $T$ with $n-1$ vertices, and upon picking the new edge swap $n$ (which is the label of the new leaf) with some other label, WLOG $1$. Also WLOG let the previous permutation $\sigma'$ of the labels be $1 \to 2 \to \cdots \to n-1 \to 1$, so $\sigma'(1)=2,\sigma'(2)=3,\ldots, \sigma'(n-1)=1$. Our new permutation $\sigma$ is equal to the old one, except now $\sigma'(n-1)=n$ and $\sigma'(n)=1$, which is still an $n$-cycle, as desired. $\blacksquare$

The most obvious thing works. Perform an induction on $n$ by deleting a leaf; say that the leaf was originally labeled $1$, and the parent of the leaf labeled $2$. Consider a complete sequence of operations on $G$; upon removing the step acting on $1$, we obtain a valid sequence of operations on $G-v$. Suppose that the $\sigma$ associated with this sequence has $\sigma(k) = 2$; then, the permutation $\sigma'$ associated with $G$ has $\sigma'(k) = 1$, $\sigma'(1) = 2$, and $\sigma'(2) = \sigma(2)$. Thus if $\sigma$ is a cycle, $\sigma'$ is a cycle too, thus the induction is complete.

Assume that at the beginning all edges of the tree are deleted. After each operation we draw the edge between the vertices that have swapped their labels. So, initially we have only isolated points and the initial permutation is the identity and consists of $n$ cycles $i\to i,i=1,2,\dots,n$. We claim that at each step two cycles merge into a larger one. Suppose that before the current step we have some $m$ connected components $\Gamma_1, \Gamma_2,\dots,\Gamma_m$ (some of them may be isolated points) and each $\Gamma_i$ corresponds to a cycle. Then we swap the labels of an edge $e=ab$ and draw it. It is not possible that $a$ and $b$ lie in the same connected component since the tree has no cycle (this is the crucial point - no cycle exists). Thus, $a\in \Gamma_i, b\in \Gamma_j, i\ne j$. It is easy to see that if we swap two values that belong to distinct disjoint cycles these two cycles merge into a larger one. Hence, at each step some two cycles merge and when all the edges are drawn we have a permutation that is a $n$ cycle.

We use strong induction on $n$. For $n=2$ (base case), we simply get $21$ from $12$ which is indeed a cycle. Let the last edge swapped be edge $uv$. Delete this edge from the tree. Then, we get two disjoint trees as a result. Both of these trees have a cycle by induction hypothesis. Let the cycles be $a_1\rightarrow a_2\cdots a_k\rightarrow a_1$ and $b_1\rightarrow\cdots b_l\rightarrow b_1$ be the cycles in tree 1 and tree 2, respectively. Here, $k+l=n$. Suppose $u=a_x,v=b_y$ and hence after removing edge $uv$, we get the combined cycle: \[a_1\rightarrow\cdots a_{x-1}\rightarrow b_y\rightarrow b_{y+1}\cdots b_l\rightarrow\cdots b_{y-1}\rightarrow a_x\rightarrow\cdots a_k\rightarrow a_1,\]as required. $\blacksquare$

I will proceed by induction, suppose that for all graphs with $n-1$ vertices when we change their labelings in such a manner they form a cycle of length $n-1$, now consider an $n$ vertice tree and remove a leef, thus we get an $n-1$ vertice cycle, now consider what happens when that leaf edge changes, we get that the leaf vertice goes to the end position of where the vertice that replaced the leaf vertice was meant to go and the rest of the vertices are not affected so its still a cycle.

The idea is that after $k$ swaps, the permutation is a bunch of cycles where the sum of (number of vertices minus one) over all cycles is exactly $k$, and that each of the cycles, if it has length $x$, has exactly $x-1$ edges in the tree with both endpoints inside the cycle, and all of them have already been used. There is really only one difficulty in showing this, which is figuring out what happens when you merge two cycles. Indeed, if you have $a_1\to a_2\to\dots\to a_s$ and $b_1\to b_2\to\dots\to b_t$, by swapping $a_s$ and $b_1$ you create the cycle $a_1\to a_2\to\dots\to a_{s-1}\to b_1\to b_2\to\dots\to b_t\to a_s\to a_1$. $\blacksquare$