yay linear algebra We wish to count the number of spanning trees of $K_n \backslash C_n$. The Laplacian matrix of this graph is the $n \times n$ matrix \begin{align*}L = D - A &=\left[ \begin{array}{ccccc} n-3 & 0 & 0 & \cdots & 0\\ 0 & n-3 & 0 & \cdots & 0\\ 0 & 0 & n-3 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \cdots & n-3 \end{array} \right] - \left[ \begin{array}{ccccc} 0 & 0 & 1 & \cdots & 0\\ 0 & 0 & 0 & \cdots & 1\\ 1 & 0 & 0 & \cdots & 1\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 1 & 1 & \cdots & 0 \end{array} \right] \\&= \left[ \begin{array}{ccccc} n-3 & 0 & -1 & \cdots & 0\\ 0 & n-3 & 0 & \cdots & -1\\ -1 & 0 & n-3 & \cdots & -1\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & -1 & -1 & \cdots & n-3 \end{array} \right] \end{align*} By Kirchhoff's Matrix Theorem, any cofactor of this matrix is the number of spanning trees of the graph. Hence \[ T_n = \det \left[ \begin{array}{cccccccc} n-3 & 0 & -1 & -1 & -1 & \cdots & -1 & -1\\ 0 & n-3 & 0 & -1 & -1 & \cdots & -1 & -1\\ -1 & 0 & n-3 & 0 & -1 & \cdots & -1 & -1\\ -1 & -1 & 0 & n-3 & 0 & \cdots & -1 & -1\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ -1 & -1 & -1 & -1 & -1 & \cdots & 0 & n-3 \end{array} \right] \] For $n$ odd, to evaluate this determinant, we only need to work in the ring $\mathbb{Z}/n\mathbb{Z}$. Thus \[\overline{T_n} = \det \left[ \begin{array}{cccccccc} -3 & 0 & -1 & -1 & -1 & \cdots & -1 & -1\\ 0 & -3 & 0 & -1 & -1 & \cdots & -1 & -1\\ -1 & 0 & -3 & 0 & -1 & \cdots & -1 & -1\\ -1 & -1 & 0 & -3 & 0 & \cdots & -1 & -1\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ -1 & -1 & -1 & -1 & -1 & \cdots & 0 & -3 \end{array} \right] = 0\] which is not easy to check; hence $n \mid T_n$. For $n$ even, let $n = 2k$. Then $T_n$ is the determinant of the $(2k-1) \times (2k-1)$ matrix: \[ T_n = \det \left[ \begin{array}{cccccccc} 2k-3 & 0 & -1 & -1 & -1 & \cdots & -1 & -1\\ 0 & 2k-3 & 0 & -1 & -1 & \cdots & -1 & -1\\ -1 & 0 & 2k-3 & 0 & -1 & \cdots & -1 & -1\\ -1 & -1 & 0 & 2k-3 & 0 & \cdots & -1 & -1\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ -1 & -1 & -1 & -1 & -1 & \cdots & 0 & 2k-3 \end{array} \right] \] Now we work in $\mathbb{Z}/k\mathbb{Z}$ and so we check that $\overline{T}_n = 0$ again, so $\frac{n}{2} = k \mid T_n$.

Perhaps I've made some grave error, but I don't think the condition that no roads join consecutive cities is at all important; the result seems to hold subject to any such symmetric condition. All the same, we'll call a spanning tree without these forbidden edges "good" and relabel the cities $1, 2, \dots, n$ with $v_1, v_2, \dots, v_0$ in that order. When $n$ is odd, good minimum spanning trees come in groups of $n$. Indeed, we can take any good spanning tree $T$ and rotate all its edges by $k$ (that is, an edge between vertices $v_i$ and $v_j$ corresponds to an edge between $v_{i + k}$ and $v_{j + k}$, indices modulo $n$) for any $0 \le k \le n - 1$ to produce another good spanning tree. We claim all $n$ such trees are distinct. Suppose, FTSOC, that a rotation of (WLOG) $T$ by $0 \le r \le n - 1$ recovered $T$. Consider an edge $v_{a}v_{b} \in T$ - rotating, we find $v_{a + tr}v_{b + tr} \in T$ for all $t \in \mathbb{N}$ - there are exactly $n /\gcd(n, r)$ of these edges since no edge is unchanged under rotation by $r$. Thus edges of $T$ come in groups of $n/\gcd(n, r)$, so that $n/\gcd(n, r) | n - 1 = |T|$. Since $r < n$, this is impossible. Thus all $n$ trees produced in this fashion are distinct, and so $n | T_n$. If $n = 2m$ is even, good minimum spanning trees come in groups of $m$. Indeed, we can take any good spanning tree $T$ and rotate all its edges by $k$ for any $0 \le k \le m - 1$ to produced another good spanning tree. Again, we claim all $m$ such trees are distinct. Suppose, FTSOC, that a rotation of (WLOG) $T$ by $0 \le r \le m - 1$ recovered $T$. Consider an edge $v_{a}v_{b} \in T$ - rotating, we find $v_{a + tr}v_{b + tr} \in T$ for all $t \in \mathbb{N}$ - there are exactly $n /\gcd(n, r)$ of these edges since no edge is unchanged under rotation by $r$. (This is why only the weaker result holds for even $n$; edges joining opposite vertices rotate to themselves if $r = m$, messing up our count). Thus edges of $T$ come in groups of $n/\gcd(n, r)$, so that $n/\gcd(n, r) | n - 1 = |T|$. Since $r < n$, this is impossible. Thus all $m = n/2$ trees produced in this fashion are distinct, and so $n/2 | T_n$.

hyperbolictangent wrote: Perhaps I've made some grave error, but I don't think the condition that no roads join consecutive cities is at all important; the result seems to hold subject to any such symmetric condition. Omg I thought I fakesolved because I found this condition wasn't needed and couldn't find what was wrong... grrr I'm so stupid. My solution was inspired by the Fermat's Little Theorem proof with coloring the beads and rotation. For this problem just note that if you can only "shift" the connections on the cities (via making a road links cities $a$ and $b$ to $a+1$ and $b+1$ instead) $n/k$ times where $k$ is an integer, then counting the total out degree you get $k$ divides $2(n-1)$ because the total outdegrees of all the cities is $2(n-1)$ and there are $k$ blocks which have the same outdegree. But then $k|\gcd(n,2(n-1))$ implying if $n$ is odd there are $n$ distinct shifting while if $n$ is even there is either $n$ or $n/2$. From there the result immediately follows. EDIT : Oops upon reading tanh's post my solution is almost identical.

I thought I fakesolved because I figured this was too easy to be on TSTST ... anyway I much prefer robinpark's solution (although I am of the opinion he should man up and do out the computation)

Since robinpark failed to finish his linear algebra approach, I'll finish for him. Take the reduced matrix robinpark wrote: For $n$ odd, to evaluate this determinant, we only need to work in the ring $\mathbb{Z}/n\mathbb{Z}$. Thus \[\overline{T_n} = \det \left[ \begin{array}{cccccccc} -3 & 0 & -1 & -1 & -1 & \cdots & -1 & -1\\ 0 & -3 & 0 & -1 & -1 & \cdots & -1 & -1\\ -1 & 0 & -3 & 0 & -1 & \cdots & -1 & -1\\ -1 & -1 & 0 & -3 & 0 & \cdots & -1 & -1\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ -1 & -1 & -1 & -1 & -1 & \cdots & 0 & -3 \end{array} \right] \] Multiply the $i^{th}$ row by $i$ ($1 \le i \le n-1$) and sum them. It's easy to see that we get a row like \[ \left[\begin{array}{ccccc} -\frac{n(n-1)}{2} & -\frac{n(n-1)}{2} & -\frac{n(n-1)}{2} & \cdots & -\frac{n(n+1)}{2} \end{array}\right] \], so the result immediately follows.

Wait but $\mathbb{Z}/n\mathbb{Z}$ is not a field for all non-prime $n$, so determinant $0$ iff has the $0$ vector in its row/column space in a nontrivial way isn't correct anymore. EDIT : Oops I am silly because that I forgot that elementary matrix operations leave the determinant invariant. I thought your post was proving the determinant was $0$ in $\mathbb{Z}/n\mathbb{Z}$ due to the fact that some linear combination of the rows formed the $0$ vector.

I don't think my previous post is wrong, but if you (dinoboy) thinks there's an issue, we don't actually have to work in $ \mathbb{Z}/n\mathbb{Z} $. Instead just take \[\left[\begin{array}{cccccccc}n-3 & 0 &-1 &-1 &-1 &\cdots &-1 &-1\\ 0 &n-3 & 0 &-1 &-1 &\cdots &-1 &-1\\ -1 & 0 &n-3 & 0 &-1 &\cdots &-1 &-1\\ -1 &-1 & 0 &n-3 & 0 &\cdots &-1 &-1\\ \vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots\\ -1 &-1 &-1 &-1 &-1 &\cdots & 0 &n-3\end{array}\right] \], and add $i$ times the $i^{th}$ $(2 \le i \le n-1)$ row to the first row to get the first row to become \[ \left[\begin{array}{ccccc}-\frac{n(n-3)}{2}&-\frac{n(n-5)}{2}&-\frac{n(n-7)}{2}&\cdots &\frac{n(n-3)}{2}\end{array}\right] \] (maybe some computation errors). Then we can pull out a $n$ or a $\frac{n}{2}$ depending on parity, and then remaining matrix is still integral, so we're done anyways.

hyperbolictangent wrote: If $n = 2m$ is even, good minimum spanning trees come in groups of $m$. I'm not sure you're using the word "group" correctly. You show that rotating a tree $T$ by $k$ for $0\le k < m$ produce $m$ distinct trees, but that doesn't imply these $m$ distinct trees rotate to each other, or even back to $T$. I think the argument you should be using is that the rotations are all invertible, which is sufficient to prove $m | T_n$

Say $x \leftrightarrow y$ if $x$ and $y$ are connected. We claim that we have cycles of lenght $n$ or $\frac{n}{2}$. Consider some pairing $A$ s.t. $i_1\leftrightarrow j_1,...,i_{n-1} \leftrightarrow j_{n-1}$ and say that lenght of cycle is $s$ and let $(n,s)=d$. Then when we consider $x \leftrightarrow y$ from $A$ either $x \leftrightarrow y $ (call it type $M$) goes to itself or we have group $x \leftrightarrow y , x+d \leftrightarrow y+d$,...,$ x+(\frac{n}{d}-1)s \leftrightarrow x+(\frac{n}{d}-1)s$ (call it type $N$). Now since all vertices participate we get $k*\frac{n}{d}+l=n$ where there is $k$ type $N$ groups and $l$ type $M$ groups. Now $l=0$ if $n$ is not even and $s=\frac{n}{2}$. Suppose this is the case, then $k|n$ contradiction (obviously $k>1$ because no tree is mapped to itself). Thus we are done.

The main idea is that we can shift the indices of all the trees and create new trees, so trees come in groups of $n$ or $n/2$. Call an index $i$ shiftable for some tree $T$ if shifting the indices of all the vertices of $T$ by $i$ creates a tree distinct from $T$. Claim. All trees $T$ are shiftable for all $0 \leq i \leq n-1$ unless $n$ is even and $i = n/2$. Suppose that some edge $xy \in T$; assume for the sake of contradiction that shifting $T$ by $i$ yields a tree isomorphic to $T$. Then, $(x+ki)(y+ki) \in T$ modulo $n$ for all $k \geq 0$. If $\gcd(n, d) = 1$ this is a contradiction because the tree must now contain $n$ distinct edges. Else, this means that all the edges must come in groups of $\frac ni$. But $\frac ni$ cannot divide $n-1$ for any $i \mid n$, so this is a contradiction as well. The only exception occurs when $i =\frac n2$ as diameters of the graph are equivalent upon shifting by $\frac n2$. $\blacksquare$ Now, if $i$ is odd, this exception is irrelevant, and we can safely conclude all trees come in groups of $n$, so $n$ divides $T_n$. If $i$ is odd, for each tree $T$, $T$ is either distinct from all its $n$ rotated copies, or else all $n$ rotated copies of $T$ come in $\frac n2$ distinct pairs. Over all $T$, this still means that $n/2$ divides $T_n$, as required.

We claim that for any valid road building $G$, we can shift the labels of the cities by $1$ taking $\pmod{n}$ a total of $n$ times creating a collective group of $n$ or $\frac{n}{2}$ distinct road buildings. This finishes the problem. Let $(d_1, d_2, \dots, d_n)$ be number of roads from cities $1, 2, \dots, n$ respectively of $G$. Note that if this multiset can be cyclically shifted right by a minimal $k$ to become itself, it is composed of identical periodic blocks of length $k$. Now the number of blocks, $\frac{n}{k}$ must satisfy $\frac{n}{k} \mid n$ and $\frac{n}{k} \mid d_1 + d_2 + \dots d_n = 2(n - 1)$, so $\frac{n}{k} \mid \gcd(n, 2(n - 1)) \implies k = n, \frac{n}{2}$. But since $k$ is also minimal we know that there are also $k$ distinct graphs that we can generated associated with $G$. We are done.