MathDB
Color graph

Source: St Petersburg Olympiad 2009, Grade 11, P6

August 30, 2017
combinatoricsgraph theory

Problem Statement

Some cities in country are connected by road, and from every city goes ≥2008\geq 2008 roads. Every road is colored in one of two colors. Prove, that exists cycle without self-intersections ,where ≥504\geq 504 roads and all roads are same color.
Back to ProblemsView on AoPS