Problem

Source: Iran TST 2014, second exam, day 1 problem 1

Tags: induction, combinatorics



Consider a tree with $n$ vertices, labeled with $1,\ldots,n$ in a way that no label is used twice. We change the labeling in the following way - each time we pick an edge that hasn't been picked before and swap the labels of its endpoints. After performing this action $n-1$ times, we get another tree with its labeling a permutation of the first graph's labeling. Prove that this permutation contains exactly one cycle.