Ре­ше­ние.

Пред­по­ло­жим, что есть два го­ро­да, между ко­то­ры­ми нет пути. Каж­дый из этих двух го­ро­дов по усло­вию со­еди­нен не менее, чем с семью дру­ги­ми го­ро­да­ми, при этом все эти го­ро­да раз­лич­ны  — ведь если какие-то два из них сов­па­да­ют, то су­ще­ству­ет путь, со­еди­ня­ю­щий ис­ход­ные го­ро­да (см. рис.). Но тогда в стра­не се­мер­ка не менее 16 го­ро­дов, что про­ти­во­ре­чит усло­вию. Сле­до­ва­тель­но, наше пред­по­ло­же­ние не­вер­но, и любые два го­ро­да свя­зы­ва­ет какой-то путь.