Рассмотрим граф со списком смежности, как указано ниже, с 4 вершинами и 4 ребрами.
1 2 3 4
1 0 1 0 1
2 1 0 1 0
3 0 1 0 1
4 1 0 1 0
Это простой прямоугольный график.
В задаче о m-раскрашиваемости графа мы должны раскрасить граф без смежных узлов одного цвета. Я читаю книгу, в которой говорится, что если степень графа равна «d», то граф можно раскрасить d + 1 способами. Но приведенный выше граф можно раскрасить двумя способами, что соответствует степени графа. Как?
