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.
Best Answer
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.