MathDB
Traveling between towns

Source: Turkey IMO TST 1993 #4

July 7, 2011
combinatorics unsolvedcombinatorics

Problem Statement

Some towns are connected by roads, with at most one road between any two towns. Let vv be the number of towns and ee be the number of roads. Prove that
(a)(a) if e<v−1e<v-1, then there are two towns such that one cannot travel between them; (b)(b) if 2e>(v−1)(v−2)2e>(v-1)(v-2), then one can travel between any two towns.
Back to ProblemsView on AoPS