TSTST 2013 Problem 7

A country has $n$ cities, labelled $1,2,3, \ldots, 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. (a) For all odd $n$, prove that $T_{n}$ is divisible by $n$. (b) For all even $n$, prove that $T_{n}$ is divisible by $n / 2$.