Нечётная раскраска графа — это такая раскраска множества его вершин в несколько иветов, что любые две соседние вершины покрашены в разный цвет и при этом для каждой вершины можно указать цвет, в который покрашено нечётное число её соседей. Барон Мюнхгаузен нарисовал граф и создал нечётную раскраску его вершин в 1022 ивета. «Вы можете мне не поверить, друзья, — говорит барон, — но на этом графе не существует нечётных раскрасок с меньшим числом цветов. Однако после того как я добавил всего одну вершину и соединил её с некоторыми вершинами этого графа, для нечётной раскраски мне понадобилось всего три цвета». Не обманывает ли нас барон?
Подсказка
Возьмем полный граф на 1022 вершинах, которые условно будем называть «толстыми». В середине каждого ребра поставим новую вершину (иными словами, мы заменяем каждое ребро этого графа на двузвенный путь).
Решение
Ответ: не обманывает.
Решение. Возьмем полный граф на 1022 вершинах, которые условно будем называть «толстыми». В середине каждого ребра поставим новую вершину (иными словами, мы заменяем каждое ребро этого графа на двузвенный путь). Новые вершины будем считать «тощими». Возьмём произвольную нечётную раскраску полученного графа. Для любых двух толстых вершин 
и 
рассмотрим тощую вершину 
, соединенную с ними. Так как у вершины в этом графе всего две соседние вершины (это как раз и ), эти вершины должны быть окрашены в разный цвет. Итак, любые две толстые вершины должны быть разного цвета, следовательно, в раскраске используется не меньше 1022 цветов.
Теперь добавим к нашему графу одну новую вершину и соединим её со всеми тощими. На полученном графе нам хватит трёх цветов: все толстые вершины красим в красный цвет, тощие — в зелёный, новую — в синий. Эта раскраска удовлетворяет требованию нечётности, поскольку у каждой красной вершины 1021 зелёный сосед, у каждой зелёной имеется один синий сосед, а у синей вершины имеется 
, т.е. нечётное число зелёных соседей.