BdMO Online Forum

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 .

A graph with $n$ vertices and $n$ edges contains a cycle. (With $n-1$ edges and no cycles it must be a tree, so the $n$th edge forms a cycle.)

$Strong$ $induction$ also gives a result .

Previously posted here http://www.matholympiad.org.bd/forum/vi ... =13&t=2928 , also pinned at the top of forum home page. Please, for common problems, search the forum at least once. Topic locked.