Страна и путешественник

[Roman Kotyk]

В стране 2007 городов, соединенных попарно дорогами таким образом, что среди любых 16 городов есть по крайней мере 15 дорог, то есть хотя бы 15 дорог, с концами в этих 16 городах. Доказать, что путешественник всегда может в этой стране найти замкнутый маршрут, который последовательно проходит через 9 городов.