TAOCP 7.2.1.6 Exercise 92
Algorithm S enumerates all spanning trees of the complete graph $K_n$ via Prüfer sequences of length $n-2$ over the alphabet ${1,2,\ldots,n}$ in lexicographic order, as established in Section 7.
Section 7.2.1.6: Generating All Trees
Exercise 92. [15] Are the first and last spanning trees visited by Algorithm S adjacent, in the sense that they have $n-2$ edges in common?
Verified: yes
Solve time: 1m41s
Solution
Algorithm S enumerates all spanning trees of the complete graph $K_n$ via Prüfer sequences of length $n-2$ over the alphabet ${1,2,\ldots,n}$ in lexicographic order, as established in Section 7.2.1.6. The correspondence between a sequence $x_1 x_2 \ldots x_{n-2}$ and a tree $T$ is a bijection: each sequence encodes exactly one labeled tree and each labeled tree yields exactly one such sequence.
Lexicographic ordering with the convention $1 < 2 < \cdots < n$ implies that the first sequence generated is
$1,1,\cdots,1 \quad (n-2 \text{ times}),$
and the last sequence is
$n,n,\cdots,n \quad (n-2 \text{ times}).$
Let $T_1$ be the tree corresponding to $1^{n-2}$ and $T_n$ the tree corresponding to $n^{n-2}$.
The Prüfer decoding rule states that a vertex $v$ appears $d(v)-1$ times in the sequence, where $d(v)$ is its degree in the tree. For $T_1$, vertex $1$ appears $n-2$ times, so $d(1)=n-1$, while every vertex $i\ge 2$ appears $0$ times, so $d(i)=1$. Thus $T_1$ is the star centered at $1$, with edge set
$E(T_1)={(1,i)\mid 2\le i\le n}.$
For $T_n$, vertex $n$ appears $n-2$ times, so $d(n)=n-1$, while every $i\le n-1$ has degree $1$. Thus $T_n$ is the star centered at $n$, with edge set
$E(T_n)={(n,i)\mid 1\le i\le n-1}.$
The intersection $E(T_1)\cap E(T_n)$ consists of edges incident to both $1$ and $n$. The only such edge is $(1,n)$, since it appears in both descriptions. Hence
$|E(T_1)\cap E(T_n)|=1.$
Two spanning trees on $n$ vertices are adjacent in the sense of the problem if and only if they share exactly $n-2$ edges. For $n\ge 4$, this requires $n-2\ge 2$, while the computed intersection size is $1$, so adjacency fails.
For $n=3$, each tree has exactly one edge. Both $T_1$ and $T_3$ contain the edge $(1,3)$, so the intersection size is $1=n-2$, and the adjacency condition holds in this degenerate case.
For $n\ge 4$, the first and last spanning trees visited by Algorithm S are not adjacent.
This completes the proof. ∎