Degrees >= 3 implies cycle not div by 3
Source: All-Russian MO 2000
December 30, 2012
combinatoricscombinatorics solved
Problem Statement
Some pairs of cities in a certain country are connected by roads, at least three roads going out of each city. Prove that there exists a round path consisting of roads whose number is not divisible by .