На плоскости нарисовано несколько точек, некоторые пары точек соединены отрезками. Известно, что из каждой точки выходит не более k отрезков. Докажите, что точки можно покрасить в k+1 цвет таким образом, чтобы любые две точки, соединенные отрезком, были покрашены в разные цвета.

В стране несколько городов (больше одного); некоторые пары городов соединены дорогами. Известно, что из каждого города можно попасть в любой другой город, проезжая по нескольким дорогам. Кроме того, дороги не образуют циклов, т.е. если выйти из некоторого города по какой-то дороге и далее двигаться так, чтобы не проходить по одной дороге дважды, то невозможно возвратиться в начальный город. Докажите, что в этой стране найдутся хотя бы два города, каждый из которых соединен дорогой ровно с одним городом.

В стране  Кривляндии 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?

   17 ученых из разных стран переписываются на одном из трех языков. Докажите, что среди них найдется тройка, в которой все ученые переписываются на одном языке.

    P.S.  Мне так понравилась эта задача, что я решил вывесить ее на сайте, ведь она с международки!