MathDB
Roads in country

Source: St Petersburg Olympiad 2008, Grade 11, P7

August 30, 2017
combinatoricsgraph theory

Problem Statement

There are 1000010000 cities in country, and roads between some cities. Every city has <100<100 roads. Every cycle route with odd number of road consists of ≥101\geq 101 roads. Prove that we can divide all cities in 100100 groups with 100100 cities, such that every road leads from one group to other.
Back to ProblemsView on AoPS