Может ли в государстве, где из каждого города выходит 3 дороги, быть ровно 100 дорог?

Нет, в государстве, где из каждого города выходит ровно 3 дороги, не может быть ровно 100 дорог.

Объясню почему.

Рассмотрим граф, где города — это вершины, а дороги — рёбра. В таком графе из каждой вершины (города) выходит 3 рёбра, то есть граф регулярный степени 3 (каждая вершина имеет степень 3).

В теории графов существует важная формула: сумма степеней всех вершин графа равна удвоенному числу рёбер. Это значит:

Сумма степеней = 2 × число рёбер

Пусть у нас $n$ городов. Из условия: из каждого города выходит 3 дороги, значит сумма степеней всех вершин будет $3n$. Тогда:

Обозначим количество дорог как $d$. Подставим:

Нам известно, что $d = 100$. Подставим:

А это нецелое число — $\frac{200}{3} \approx 66.67$. Но количество городов не может быть дробным, оно должно быть целым числом. Следовательно, при 100 дорогах невозможно, чтобы из каждого города выходило ровно 3 дороги.

Вывод: в таком государстве не может быть ровно 100 дорог.