Problem

Source: Turkey IMO TST 1993 #4

Tags: combinatorics unsolved, combinatorics



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