Граф — граф Кнезера $K(5,2) =$ граф Петерсена. Его хроматическое число равно χ = 5 — $2\cdot 2 + 2 = 3$ по формуле Ловаса (χ$(K(n,k)) = n$ — $2k + 2$). Здесь $n=5, k=2$: χ = 5 — $4 + 2 = 3$. Максимальная клика: два непересекающихся $2-$элементных подмножества {1,2} и {3,4} — клика из 2 (рёбер между несмежными). Клика из 3: {1,2},{3,4},{...} — нет трёх попарно непересекающихся $2-$подмножеств {1,2,3,4,5}. Таким образом $\omega =2$, но χ=3. Раскраска: {1,2},{1,3},{1,4},{1,5} $\to$ цвет 1; {2,3},{2,4},{2,5} $\to$ цвет 2; {3,4},{3,5},{4,5} $\to$ цвет 3. Проверим: смежны лишь непересекающиеся; в каждом цвете все подмножества содержат общий элемент — попарно пересекаются — значит смежных нет. Ответ: χ = 3.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!