Ответ:
Возьмем два города не соединенных между собой. Каждый из них соединен как минимум с тремя городам, тогда получается две отдельные друг от друга ветки по 4 города, то есть 4 + 4 = 8 городов, то невозможно по условию задачи. Значит хотя бы один город из этих двух веток является общим, а значит из любого города можно доехать до любого другого (возможно, проезжая через другие города).
:)