Без доказательства.
Уже сто лет математики пытаются доказать знаменитую нерешенную проблему теории графов – гипотезу четырех красок.
Гипотеза 4 красок. Всякий планарный граф 4-раскрашиваем.
При попытках доказательства этой гипотезы были получены некоторые интересные результаты:
1) если гипотеза четырех красок не верна, то любой опровергающий пример будет очень сложным; известно, например, что всякий планарный граф, имеющий менее 52 вершин 4-раскрашиваем;
2) любой, не содержащий треугольников, планарный граф 3-раскрашиваем (теорема Грёча);
3) если доказывать гипотезу четырех красок, то достаточно доказать ее для гамильтоновых графов (результат Уитни).
1. Акимов О.Е. Дискретная математика. Логика, группы, графы. – М.: Лаборатория базовых знаний, 2001.
2. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория базовых знаний, 2002.
3. Новиков Ф.А. Дискретная математика для программистов. – Издательство: Питер, 2003.
4. Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969.
5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 1992.