Ответ:

1) Нет. Например, города могут быть разделены на две группы по четыре города, внутри каждой группы все города соединены дорогами друг с другом, а между группами дорог нет. Из каждого города выходит по три дороги, но добраться из одной группы в другую нельзя.

2) Да. Представим города вершинами графа, а дороги — рёбрами. Если бы граф был несвязным, в каждой его отдельной связной части было бы не менее пяти городов: иначе у города в части не могло бы быть четырёх различных соседей. Две такие части вместе содержали бы не менее десяти городов, но городов всего восемь. Значит, граф связен, и между любой парой городов существует путь.

Ответ: 1) нет; 2) да.