Районная олимпиада, 2001-2002 учебный год, 9 класс

В некотором государстве система авиалиний устроена так, что любой город соединен авиалиниями не более, чем с тремя другими городами и из любого города в любой другой город можно перелететь, сделав не более одной пересадки. Какое наибольшее число городов может быть в этом государстве?

Комментарий/решение

Из фиксированного города можно проехать без пересадки не более чем в три города, а из каждого из этих городов — еще не более чем в два отличных от города. Поскольку в каждый город можно долететь из не более чем с одной пересадкой, то всего в государстве не более 10 городов. Между 10 городами, сообщение с наблюдением условий задачи можно установить,