\[\boxed{\mathbf{1150\ (1142)}\mathbf{.}\mathbf{\ }Еуроки\ - \ ДЗ\ без\ мороки}\]
\[Возьмем\ два\ города\ не\ \]
\[соединенных\ между\ собой.\ \]
\[Каждый\ из\ них\ \]
\[соединен\ как\ минимум\ с\]
\[\ тремя\ городам,\ тогда\]
\[\ получается\ две\ \]
\[отдельные\ друг\ от\ друга\ ветки\ \]
\[по\ 4\ города,\ то\ есть\]
\[\ 4\ + \ 4\ = \ 8\ городов,\ \]
\[что\ невозможно\ по\ \]
\[условию\ задачи.\ \]
\[Значит,\ хотя\ бы\ один\ город\ \]
\[из\ этих\ двух\ веток\ является\ \]
\[общим,\ \ \]
\[и\ тогда\ из\ любого\ города\ \]
\[можно\ доехать\ до\ любого\]
\[\ другого\ \]
\[(возможно,\ проезжая\ через\ другие\ города).\]