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