Условие
В цикле из пяти вершин соседние вершины должны иметь разные цвета. Найдите минимальное число цветов и приведите раскраску.
Решение по шагам
Попробуем два цвета. После выбора цвета первой вершины следующие вынужденно чередуются. У пятой вершины получается тот же цвет, что у первой, но они соседствуют: противоречие. Поэтому двух цветов недостаточно.
Три цвета подходят: по порядку вершин используем A,B,A,B,C. Каждая из пяти соседних пар имеет разные цвета. Нижняя оценка и явная конструкция вместе доказывают, что хроматическое число равно 3.
Проверка результата
Перебор всех 2⁵ раскрасок не находит допустимой; среди 3⁵ вариантов допустимые есть. Приведённая строка ABABC проверяется по всем пяти рёбрам, включая замыкающее.
Типичная ошибка
Проверять только четыре последовательных ребра нельзя: последнее ребро возвращается к первой вершине и создаёт препятствие.
Что даёт этот метод
Чётный цикл можно раскрасить двумя цветами, нечётный требует трёх. Наличие нечётного цикла препятствует двудольности графа.
Дальше по теме
Комбинаторика и дискретная математика: другие задачи и разборы.
Учебное условие и объяснение сформулированы редакцией damirock.com. Это самостоятельный разбор, а не официальный билет или ключ экзамена. Числа относятся к модели задачи.