Berkeley Math Circle

Solution:

If we consider the cities to be vertices and the roads to be edges, this arrangement is a type of graph known as a trivalent tree. We will find a general formula in terms of $n$ for the number of trivalent trees on $2n$ vertices.

We can construct such a tree as follows. First, we will choose the internal vertices (non-leaves) of $T$. If there are $i$ internal vertices, then summing the degrees over all vertices we get
$$2 \cdot (\# \text{ of edges}) = 2 \cdot (2n-1) = i \cdot 3 + (2n-i) \cdot 1 = 2i + 2n.$$
Solving for $i$ gives $i = n-1$, so there are $\left(\begin{array}{c}2n \\ n-1\end{array}\right)$ ways to choose the internal vertices. Now imagine attaching two edges to each of these $n-1$ vertices (with the other endpoint of each edge not yet chosen). This is $2n-2$ edges total, so all but one edge of the graph. We can think of the other endpoint of each edge as a position that needs to be filled, so at the start there are $2n-2$ available positions. Now, go through the leaves in increasing order, and for each leaf, choose an edge to attach it to. The number of available edges starts at $2n-2$ and goes down by one at each step as one position gets taken, so the number of ways to do this is $(2n-2)(2n-3) \ldots (n-2)$. After all the leaves are added, there must be at least one internal vertex both of whose edges are filled, since there are $n-1$ internal vertices and only $n-3$ unfilled edges left. Find the smallest such vertex, and choose an open edge to attach it to, which can be done in $n-3$ ways. Now that vertex has all three of its neighbors chosen.

After that, there are $n-2$ remaining internal vertices and $n-4$ available edges, all of which are attached to one of those vertices. So again, there must be a vertex both of whose edges are filled, so we can take the smallest such vertex and choose any of the $n-4$ edges to attach it to. We can continue this process until every internal vertex except for two of them has three edges, and at that point, we must add the final edge between those two vertices.

After this process is complete, we have a trivalent tree, but each such tree has been counted $2^{n-1}$ times, because we considered the two edges coming out of each internal vertex to be distinct, when actually they should not be. Thus, we must divide by $2^{n-1}$, implying that the total number of trivalent trees is
$$\left(\begin{array}{c} 2n \\ n-1 \end{array}\right) \cdot \frac{(2n-2)(2n-3) \cdot \ldots \cdot 2 \cdot 1}{2^{n-1}} = \frac{(2n)!}{(n+1)!}(2n-3)!!$$
Plugging in $n=1011$ gives the desired expression.