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

Рассмотрим, возможно ли построить граф, удовлетворяющий этим условиям. Если в графе есть города с пятью дорогами, то их степень равна 5. Если есть города с четырьмя дорогами, их степень равна 4. Сумма всех степеней графа должна быть четной, так как каждую дорогу считают для обоих концов. Однако при данных условиях это не выполняется. Поэтому такой граф невозможен, и ответ: Нет.