Problem

Source: St Petersburg Olympiad 2014, Grade 10, P7

Tags: combinatorics, graph theory



Some cities in country are connected with oneway road. It is known that every closed cyclic route, that don`t break traffic laws, consists of even roads. Prove that king of city can place military bases in some cities such that there are not roads between these cities, but for every city without base we can go from city with base by no more than $1$ road.

HIDE: PS I think it should be one more condition, like there is cycle that connect all cities