MathDB

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.

Problem Statement