Take a graph with each city as a node and each 2-way route as an edge. Then we have $2000$ edges in the graph with $64$ nodes and we want to show that this graph is connected. However $2000 > \frac{1}{2}(64^2 - 3\cdot 64 + 4)$ and so this graph has a Hamiltionian path, which shows that it is connected.