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

Пусть в государстве \(n\) городов. Если из каждого города выходит 3 дороги, то сумма степеней всех вершин (городов) графа равна \(3n\). С другой стороны, сумма степеней всех вершин графа должна быть равна удвоенному числу ребер (дорог), то есть \(2 \cdot 100 = 200\). Таким образом, должно выполняться равенство \(3n = 200\). Так как 200 не делится на 3, то такого государства быть не может.