Problem: A country has $n$ cities, labelled $1,2,3,\dots,n$.
It wants to build exactly $n-1$ roads between certain pairs of cities
so that every city is reachable from every other city via some sequence of roads.
However, it is not permitted to put roads between pairs of cities
that have labels differing by exactly $1$,
and it is also not permitted to put a road between cities $1$ and $n$.
Let $T_n$ be the total number of possible ways to build these roads.
\begin{enumerate}[(a)]
  \ii For all odd $n$, prove that $T_n$ is divisible by $n$.
  \ii For all even $n$, prove that $T_n$ is divisible by $n/2$.
\end{enumerate}

Solution: You can just spin the tree!

Fixing $n$, the group $G = \ZZ/n\ZZ$ acts on the set of trees
by rotation (where we imagine placing $1,2,\dots,n$ along a circle).

\begin{claim*}
  For odd $n$, all trees have trivial stabilizer.
\end{claim*}
\begin{proof}
  One way to see this is to look at the degree sequence.
  Suppose $g^e$ fixes a tree $T$.
  Then so does $g^k$, for $k = \gcd(e,n)$.
  Then it follows that $n/k$ divides $\sum_v \deg v = 2n-2$.
  Since $\gcd(2n-2, n) = 1$ we must then have $k = n$.
\end{proof}

The proof for even $n$ is identical except that $\gcd(2n-2, n) = 2$
and hence each tree either has stabilizer with size $\le 2$.

There is also a proof using linear algebra,
using Kirchoff's tree formula.  (Overkill.)