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