На плоскости нарисовано несколько точек, некоторые пары точек соединены отрезками. Известно, что из каждой точки выходит не более k отрезков. Докажите, что точки можно покрасить в  k + 1  цвет таким образом, чтобы каждые две точки, соединенные отрезком, были покрашены в разные цвета. 
   Индукция по числу точек. База: для одной точки утверждение очевидно. 
   Шаг индукции. Пусть на плоскости нарисовано  n + 1  точек, некоторые пары из которых соединены отрезками. Рассмотрим одну из точек - A. На время забудем про неё и про выходящие из неё отрезки. По предположению индукции оставшиеся n точек можно покрасить в  k + 1  цвет таким образом, чтобы каждые две точки, соединённые отрезком, были покрашены в разные цвета. Покрасим эти n точек нужным образом. Вспомним про точку A. Она соединена отрезками  не более, чем с k точками. Поскольку цветов  k + 1,  покрасим  точку A в цвет, отличный от цветов точек, с которыми она соединена. Тем самым, получена требуемая раскраска точек. 
Степень вершины Индукция (прочее)