Эйлеровы графы

Назовём город “захолустным”, если из него идёт не более двух дорог. Сотрём с карты страны любой захолустный город, если таковой имеется, вместе с выходящими из него дорогами. Подчистим таким же образом новую карту и будем продолжать стирание захолустных городов, пока они не исчезнут. Число дорог, которые мы при этом можем стереть, не превосходит ; поэтому хотя бы один город останется.

Выберем любой из оставшихся городов. Из него, как и из других оставшихся городов, выходят по меньшей мере три дороги. Пойдём по одной из них и каждый раз, приходя в новый город, будем двигаться дальше по одной из дорог, отличных от дороги, по которой мы пришли. Если какие-нибудь два маршрута, состоящие не более чем из 10 дорог, закончатся в одном городе, то мы получим искомый кольцевой маршрут не более чем из 20 дорог. В противном случае число всех таких маршрутов не меньше чем , а число городов, то есть возможных концов этих маршрутов — не больше 1988. Противоречие.