|
|
 |
Условие
У выпуклого многогранника одна вершина A имеет степень 5, а все остальные – степень 3. Назовём раскраску рёбер многогранника в синий, красный и лиловый цвета хорошей, если для каждой вершины степени 3 все выходящие из нее ребра покрашены в разные цвета. Оказалось, что количество хороших раскрасок не делится на 5. Докажите, что в одной из хороших раскрасок какие-то три последовательных ребра, выходящие из A , покрашены в один цвет.
Решение
Рассмотрим произвольную хорошую раскраску. Заметим, что общее число концов рёбер каждого цвета чётно; при этом в каждой вершине степени 3 количество концов каждого цвета имеет одинаковую чётность (их там по одному). Поэтому и в вершине A чётность их количеств также одинакова; тогда все они нечётны, и в ней сходится три ребра одного цвета и по одному ребру остальных.
Предположим, что нет хорошей раскраски с тремя последовательными рёбрами одного цвета, выходящими из одной вершины. Докажем, что тогда количество хороших раскрасок, в которых из A выходит три синих ребра, делится на 5. Тогда, очевидно, и общее количество хороших раскрасок будет делиться на 5, что противоречит условию.
Пусть из вершины A последовательно выходят ребра AB1, AB2, AB3, AB4 и AB5 (далее по циклу опять идет ребро AB1). В любой раскраске красное и лиловое рёбра из A идут не подряд (иначе и три синих ребра идут подряд). Следовательно, для концов красного и лилового ребер есть 5 вариантов: (B1, B4), (B2, B5), (B3, B1), (B4, B2), (B5, B3); обозначим соответствующие количества раскрасок через k14, k25, k31, k42, k53. Мы докажем, что
k14 ≤ k42 ≤ k25 ≤ k53 ≤ k31 ≤ k14, откуда будет следовать, что все пять чисел равны, а общее количество раскрасок делится на 5.
Покажем, что k25 ≤ k53 (остальные неравенства аналогичны). Пусть в некоторой раскраске рёбра AB2 и AB5 – не синие (пусть для определенности AB2 красное). Рассмотрим граф, вершинами которого являются вершины многогранника, а рёбрами – синие и красные рёбра. Тогда степень вершины A равна 4, а степени остальных вершин – по 2. Отсюда сразу следует, что граф распался на несколько циклов, причём два из них пересекаются только по вершине A , а остальные не пересекаются вовсе. Рассмотрим цикл, проходящий через A и содержащий AB2; тогда он содержит ещё и синее ребро, выходящее из A. Перекрасив синие рёбра этого цикла в красные и наоборот, мы получили другую хорошую раскраску.
При этом возможны три случая (см. рис.). Если цикл содержит синее ребро
AB1 или AB4 , то после перекраски три последовательных ребра (AB2, AB3, AB4 или AB1, AB2, AB3) окрашены в синий цвет; это невозможно по предположению. Значит,
в цикле есть ребро AB3, и после перекрашивания получилась раскраска, в которой красное и лиловое ребра – AB3 и AB5. При этом из разных раскрасок после перекрашивания получались разные, так как исходная раскраска восстанавливается по новой аналогичной процедурой. Поэтому k25 ≤ k53, что и требовалось.
Замечания
1. Легко видеть, что мы нигде не пользовались специфическими особенностями многогранника. Зафиксировав некоторую (вообще говоря, произвольную) циклическую нумерацию B1, B2, B3, B4, B5 соседей вершины A, мы доказали существование хорошей раскраски, в которой в один цвет покрашены три ребра, идущих из A к последовательным в этой нумерации вершинам.
2. Предположим, что в нашем многограннике есть хорошие раскраски, но откажемся от условия, что их количество не кратно 5. Сделаем еще более смелое предположение, что нам в таких условиях удалось доказать наличие хорошей раскраски, в которой три последовательных ребра, выходящие из A, покрашены в один и тот же цвет. Отсюда без труда выводится самое известное (без преувеличения!) утверждение в теории графов – гипотеза четырёх красок.
