Олимпиадная задача по теории графов: кольцевой маршрут в 1988 городах (9-10 класс)

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

  Выберем любой из оставшихся городов. Из него, как и из других оставшихся городов, выходят по меньшей мере три дороги. Пойдём по одной из них и каждый раз, приходя в новый город, будем двигаться дальше по одной из дорог, отличных от дороги, по которой мы пришли. Если какие-нибудь два маршрута, состоящие не более чем из 10 дорог, закончатся в одном городе, то мы получим искомый кольцевой маршрут не более чем из 20 дорог. В противном случае число всех таких маршрутов не меньше чем  3(1 + 2 + 2² + ... + 2⁹) = 3(2¹⁰ – 1) = 3069,  а число городов, то есть возможных концов этих маршрутов – не больше 1988. Противоречие.