Европа · вопрос Гатри к де Моргану, 1852
Хватит ли четырёх красок
Как звучало тогда
Студент попросил меня объяснить ему факт, о котором я не знал и до сих пор не знаю, правда ли он. Он говорит, что если фигура как-либо разделена и части её раскрашены так, что соседние по границе имеют разные цвета, то четырёх красок довольно.
Условие
Построить карту, которую нельзя раскрасить тремя красками так, чтобы соседние по границе области были разного цвета. Можно ли построить карту, требующую пяти красок?
Показать ответ
трёх мало уже для четырёх попарно соседних областей; карты, требующей пяти, не существует — но доказано это лишь в 1976 году
О чём эта задача
Построить карту на четыре краски может пятиклассник: возьмите одну область и окружите её тремя, попарно соприкасающимися. А вот доказать, что пяти никогда не понадобится, не удавалось 124 года. Заметим, чего в задаче нет: размеров, формы, расстояний — важно только, кто с кем граничит. Это и есть переход к графу, тот же самый, что сделал Эйлер с кёнигсбергскими мостами. Пять областей, попарно соседних, на плоскости не разместить — но из этого ещё не следует, что четырёх красок хватит, и вся трудность именно здесь.
Разбор — «как решали тогда» и «как решают сейчас» — для этой задачи ещё не написан.