В стране несколько городов (больше одного); некоторые пары городов соединены  дорогами. Известно, что из каждого города можно попасть в любой другой, проезжая по нескольким дорогам. Кроме того, дороги не образуют циклов, то есть если выйти из некоторого города по какой-то дороге и далее двигаться так, чтобы не проходить по одной дороге дважды, то невозможно возвратиться в начальный город. Докажите, что в этой стране найдутся хотя бы два города, каждый из которых соединен дорогой ровно с одним городом. 
   Первый способ. Рассмотрим самую длинную цепь из дорог, то есть возьмём самую длинную последовательность попарно различных городов  A1, A2, ..., Ak, в которой каждые два соседних города в этой последовательности соединены дорогой. Докажем, что из городов A1 и Ak выходит ровно одна дорога (соответственно в A2 и Ak–1). Пусть, например, из A1 идет дорога в некоторый город B, отличный от A2. Если B – один из городов A3, ..., Ak, то возникает цикл из дорог, что противоречит условию. Таким образом, город B отличен от городов A1, A2, ..., Ak. Следовательно, в последовательности городов B, A1, A2, ..., Ak города попарно различны и соседние города соединены дорогой. Но эта последовательность содержит больше k городов вопреки выбору последовательности A1, A2, ..., Ak. 
Деревья Принцип крайнего  (прочее)