Travelling to the point of origin without using the same road twice BdMO 2013 Secondary:

There are  $n$  cities in a country. Between any two cities there is at most one road. Suppose that the total number
  of roads is $n$. Prove that there is a city such that starting from there it is possible to come back to it without ever 
  travelling the same road twice.

I feel like I should be using the Pigeonhole Principle somewhere.We check for $n=2$.However for $n=2$,there are only $2$ cities and only $1$ road that connects them.Therefore,n cannot be equal to $2$.$n=3$ and everything larger than $3$ works fine.It is also important to note that when $n>3$,there exists at least  $2$ cities that are not connected to one another.However,$n$ number of cities imply $\dbinom{n}{2}$ number of roads.But I still cannot deduce any useful information from my observations.A hint will be appreciated.
 A: Suppose the statement is true for $S(n)$.  Let us try showing the statement holds for $S(n+1)$ by adding a city C.
If C does not have a road connecting it, then we can eliminate C and any random road from the graph and we must still have a solution by $S(n)$.  Similarly, if C has only one road connecting it to some other city, the same logic yields a solution after removing C and its road.
Now let C have two roads connecting it to cities A and B.  If A and B are connected directly, we have a cycle in ABC.  Otherwise we can imagine C and its roads as one road connecting these A and B, hence again we have by $S(n)$ a solution.
Lastly, if C is connected by $3$ or more roads to different cities, we must have at least one city (say D) in the country connected to utmost one road.  (This is because if every city other than C has two or more roads, we must have $\ge \frac{2n+3}{2} > n+1$ roads.)  Remove the city D and any road connected to it (or a random road if D is not connected) and we must have a solution again by $S(n)$.
As you have shown $S(3)$ holds, the rest follows from induction.  
