Чётность

Будем называть разноцветной звёздочкой город и три дороги, выходящие из него, если цвета этих дорог попарно различны. Тогда каждый город даёт разноцветных звёздочек, а всего их что является чётным числом. Назовём плохой четвёрку, которая не является хорошей. Докажем, что в плохой четвёрке количество разноцветных звёздочек чётно. Единственным плохим случаем может быть три разноцветных звёздочки. Тогда пусть в четвёрке города Не теряя общности, будем считать дорогу цвета 1, дорогу цвета 2, дорогу цвета 3. Также будем считать звёздочки вершин разноцветными. Тогда дорога обязана быть цвета 3, дорога — цвета 2, а дорога — цвета 1. Но тогда и звёздочка для будет разноцветной, противоречие. Таким образом, количество разноцветных звёздочек нечётно только в хороших четвёрках. Поскольку общее число разноцветных звёздочек чётно, получаем требуемое.