теория-графов - Способ раскраски графа

Здесь не сказано, что $%n$% -- это число вершин, но я так понимаю, что это подразумевалось.

В такой формулировке раскраска не всегда возможна: легко привести контрпример. А именно, рассмотрим полный граф на 4 вершинах, и ещё одну дополнительную вершину, которая ни с чем не соединена. При этом $%n=5$%, $%k=3$% нечётны, но раскраска в три цвета невозможна. Чтобы рассуждение проходило, граф надо считать связным.

При этом дополнительном предположении мы сначала заключаем, что граф не является регулярным степени $%k$%. Если бы имела место эта ситуация, то число рёбер было бы равно $%nk/2$%, но есть оно не целое (лемма о рукопожатиях). Далее индукцией по числу вершин, без предположений о нечётности, доказываем, что если граф связен, и степени всех его вершин не больше $%k$%, и при этом имеется вершина степени $%< k$%, то граф $%k$%-раскрашиваем.

База индукции очевидна. Шаг: берём вершину $%v$% степени $%< k$% и временно удаляем её вместе со всеми исходящими рёбрами. При этом может возникнуть не связный граф. Однако в каждой связной компоненте имеется вершина, которая в предыдущем графе была соединена с $%v$%. Поэтому её степень в подграфе будет строго меньше $%k$%. Тогда все связные компоненты по предположению индукции будут $%k$%-раскрашиваемы. После этого добавляем $%v$%, и подбираем для неё цвет. Она соединена менее чем с $%k$% уже раскрашенными вершинами, и тогда какой-то из $%k$% цветов не задействован. В него и раскрасим $%v$%.