Kvant Math Problem 2858

Consider a tree with $n$ vertices, each initially containing a single chip.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 20m14s
Source on kvant.digital

Problem

A tree is given (i.e., a connected graph without cycles). Initially, each of its vertices contains one chip. On a move, an edge is chosen, and the two chips at the ends of this edge are swapped. Prove that if one performs (in some order) one move for each edge, then as a result the chips will be shifted in a cycle relative to their initial positions (i.e., the chips can be numbered 1, 2, ..., $n$ so that chip 1 ends up in the initial position of chip 2, chip 2 in the initial position of chip 3, ..., chip $n$ in the initial position of chip 1). Figure 1 shows an example for $n=5$.

Figure 1

Folklore

Exploration

Consider a tree with $n$ vertices, each initially containing a single chip. A move consists of selecting an edge and swapping the chips at its endpoints. If the edges of the tree are used exactly once, in an arbitrary order, the operation on the chips defines a permutation of the vertices. The goal is to prove that this permutation is always a single $n$-cycle, meaning that the chips are cyclically shifted relative to their initial positions.

A natural approach is to represent each edge ${x,y}$ as the transposition $(x,y)$ in the symmetric group $S_n$. For any sequence of edges $e_1, e_2, \dots, e_{n-1}$, let $t_i$ denote the transposition corresponding to $e_i$. Then the resulting permutation of the chips is

$\pi = t_{n-1} t_{n-2} \cdots t_1.$

This reduces the problem to showing that any product of the edge transpositions corresponding to the tree, taken in any order, is a single $n$-cycle.

The strategy is to use induction on the number of vertices. For the induction step, a leaf vertex is removed, the induction hypothesis is applied to the smaller tree, and then the effect of the leaf edge is incorporated into the existing cycle. The key algebraic fact is that conjugating a transposition by a permutation correctly inserts the new vertex into the cycle.

Problem Understanding

Let $T$ be a tree with vertex set $V$ and edge set $E$. Label the vertices $1, 2, \dots, n$ and associate each edge ${x,y} \in E$ with the transposition $(x,y)$ in $S_n$. If the edges are used in some order $e_1, e_2, \dots, e_{n-1}$, the resulting permutation is

$\pi = t_{n-1} t_{n-2} \cdots t_1,$

where $t_i$ corresponds to $e_i$. The problem is to prove that $\pi$ is an $n$-cycle for any ordering of the edges.

Proof Architecture

The proof proceeds by induction on the number of vertices $n$. The base case $n=2$ is immediate. For $n>2$, select a leaf vertex $v$ with unique neighbor $u$ and consider the edge $e_k = {u,v}$ in the given sequence. Removing $v$ and $e_k$ produces a tree $T'$ on $n-1$ vertices. Every transposition in the product $\pi$ either involves $v$ exactly once or acts only on $T'$. Denote by $A$ the product of transpositions after $e_k$ and by $B$ the product before $e_k$, so that $\pi = A (u,v) B$. Since $A$ and $B$ involve only vertices of $T'$, they fix $v$.

Define $\sigma = BA$, which is a product of all edges of $T'$ in some order. By the induction hypothesis, $\sigma$ is an $(n-1)$-cycle on $T'$. The goal is then to show that inserting $v$ via the transposition $(u,v)$ produces a single $n$-cycle. The correct conjugation is

$A(u,v)A^{-1} = (A(u),v).$

Setting $w = A(u)$ ensures that the new vertex is inserted properly into the cycle of $T'$.

Solution

Let the edges of the tree be used in some fixed order $e_1, e_2, \dots, e_{n-1}$. Associate each edge $e_i = {x,y}$ with the transposition $t_i = (x,y)$, so that the resulting permutation is

$\pi = t_{n-1} t_{n-2} \cdots t_1.$

We prove by induction on $n$ that $\pi$ is an $n$-cycle.

For $n=2$, the tree consists of a single edge connecting two vertices. The corresponding transposition swaps these two vertices, producing a $2$-cycle, which establishes the base case.

Assume that the statement is true for all trees with $n-1$ vertices. Let $T$ be a tree with $n$ vertices. Choose a leaf $v$ with unique neighbor $u$ and let $e_k = {u,v}$ denote the position of this edge in the sequence. Writing the product for $\pi$ and isolating the factor corresponding to $e_k$ gives

$\pi = A (u,v) B,$

where

$A = t_{n-1} \cdots t_{k+1}, \quad B = t_{k-1} \cdots t_1.$

Every transposition in $A$ and $B$ involves only vertices of $T' = T \setminus {v}$ and thus fixes $v$.

Define

$\sigma = BA.$

The factors of $\sigma$ are exactly the transpositions corresponding to the edges of $T'$, in the order inherited from the original sequence after removing $e_k$. By the induction hypothesis, $\sigma$ is an $(n-1)$-cycle on $T'$.

Conjugating $(u,v)$ by $A$ gives

$A (u,v) A^{-1} = (A(u),v).$

Set $w = A(u)$, which belongs to $T'$. Then

$\pi = A (u,v) B = (A (u,v) A^{-1}) (AB) = (w,v) (AB).$

Moreover, $AB$ and $BA = \sigma$ are conjugate, so $AB$ is also an $(n-1)$-cycle on $T'$. Denote this cycle by

$\rho = (w, a_2, a_3, \dots, a_{n-1}).$

Then

$(w,v)\rho = (w, a_2, a_3, \dots, a_{n-1}, v).$

Indeed, $w \mapsto a_2$, $a_2 \mapsto a_3$, $\dots$, $a_{n-1} \mapsto v$, and $v \mapsto w$. Hence $(w,v)\rho$ is a single cycle containing all $n$ vertices. Therefore $\pi$ is an $n$-cycle. This completes the induction.

Verification of Key Steps

The induction does not require the leaf edge to appear in any special position in the sequence. Isolating the transposition corresponding to the leaf is valid regardless of order. The induction hypothesis applies to $T'$ with the inherited order, which can be arbitrary. The conjugation formula $A(u,v)A^{-1} = (A(u),v)$ correctly identifies the image of $u$ under $A$, ensuring that the new vertex $v$ is properly inserted into the $(n-1)$-cycle of $T'$. This guarantees that the final permutation $\pi$ is an $n$-cycle. The group-theoretic reasoning for multiplying a cycle by a transposition is elementary and fully justified.

Alternative Approaches

An equivalent argument can be formulated in terms of chip trajectories. Removing a leaf reduces the tree to $T'$, whose chips form an $(n-1)$-cycle. The swap along the leaf edge inserts the leaf's chip into the existing cycle, yielding an $n$-cycle. This trajectory-based argument mirrors the permutation argument but requires tracking chip positions dynamically. The algebraic proof presented above isolates the leaf transposition and applies induction directly to the permutation, yielding a concise and rigorous solution. ∎