математика - Немного комбинаторики. Графы

Это доказывается по индукции. Для треугольника утверждение очевидно. Пусть $%n\ge4$%. Считаем, что для многоугольников с меньшим числом сторон всё уже доказано. Если диагоналей не проведено, то чередуем цвета вершин, и если в конце не сходится, то одну из вершин раскрашиваем в третий цвет. Если диагонали есть, то выбираем из них "крайнюю", то есть такую, которая разделяет многоугольник на два многоугольника $%M_1$% и $%M_2$%, где $%M_1$% не имеет диагоналей. Раскрашиваем $%M_2$%; это можно сделать по предположению индукции, так как в нём меньше вершин. Остаётся раскрасить вершины ломаной, в которой концы уже раскрашены. Это также делается чередованием цветов, пока не дойдём до последней не раскрашенной вершины ломаной. Для неё один из трёх цветов подойдёт, так как у неё всего две соседних.

Я всё-таки напишу здесь решение второй задачи. Число входящих рёбер равно числу выходящих, и оно не превосходит $%dn$%, где $%n$% -- число вершин. Из этого следует, что найдётся вершина, в которую входит не более $%d$% рёбер. Удалим её вместо со всеми входящими и выходящими рёбрами. Получится граф с меньшим числом вершин, где выходящих из каждой вершины рёбер по-прежнему не больше $%d$%. Рассуждая по индукции, раскрасим его вершины в $%2d+1$% цвет (правильным образом). Теперь вернём на место удалённую вершину. Она соединена не более чем с $%2d$% вершинами, цвета которых определены. Раскрашиваем её в тот цвет, которого среди них нет.

Базу индукции я не рассматривал, но она очевидна: при $%d=0$% рёбер нет, и одного цвета хватает.