Problem involving n cities and n roads connecting between them

Question

A problem was given as follows:

Consider there are $n$ cities and between any two cities there is at most one road. In all there are a total of $n$ number of roads forming a connection between those $n$ cities. Show that there exists one city such that starting from there it is possible to come back to it without ever travelling the any road twice.

Please help with a solution to this problem.

Answer 1

We can prove this by induction on $n$. The case $n=3$ is the smallest possible, and is easy to handle.

First, suppose that there is some dead end, meaning a town with only one road out of it. If we delete that town and its road, then we have a network of $n-1$ cities and $n-1$ roads, which by induction has a "cycle" (route which starts and ends at a town without reusing roads). This cycle also exists in the original network, where the deleted city and road are re-added.

Otherwise, every town either has either zero roads out of it, or at least two roads. Let $v_0$ be a town with two or more roads out of it; call this $v_0$. Starting at $v_0$, drive from town to town without reusing any roads, until you get stuck, because you are in a town where all roads out of it have been used. That is, we choose a sequence $$ v_0,v_1,v_2,\dots,v_n $$ of cities, where the roads connecting $v_i$ to $v_{i+1}$ for $i=0,1,\dots,n-1$ are distinct, and which cannot be extended any further. We got stuck at city $v_n$. Since we assumed there are no dead ends (this case was handled in the last paragraph), we must have visited $v_n$ at a previous point. Letting $v_m$ be an earlier occurrence of $v_n$, then $v_m\to v_{m+1}\to \dots \to v_{n-1}\to v_n$ is the desired route.

Answer 2

We can consider all cities to be connected. If they are not, we only look at the different subset of cities that are connected. It is easy to see that at least one of them has at least the same amount of streets than cities. Thus, we just look at that subset to get back to the "all cities are connected" case.

With $n$ connected cities, we need $n-1$ streets to connect them in some way. No two cities can be connected more than once, thus we have one additional road to connect two cities $A$ and $B$. But this creates a loop, starting at $A$, going through the normal connection road to $B$ and then back to $A$ over the newly created road.

Thus, city $A$ fulfills the condition to be able to traverse a loop without ever using the same road twice.