Проблема четырёх красок

[programer19]

Всем привет.

Не могу понять в чём заключается проблема доказательства, что его проводят только на компьютере. Ведь если формализовать задачу, то её можно привести к теории графов. Тогда доказательство становится элементарным: полный граф K₅ невозможно распутать (по меньшей мере 2 его ребра всегда будут пересекаться), а значит области карты не могут граничить между собой по принципу "каждая с каждой" и если взять любые 5 областей на карте, то 2 из них обязательно не будут соприкасаться, что позволит их покрасить в один цвет. Таким образом достаточно четырёх красок для закраски абсолютно любой карты.

Как доказать что граф K₅ нельзя распутать? Элементарно: распутав граф K₄, мы получим 4 области, разделённые рёбрами графа. Но каждая из этих областей граничит только с тремя точками, а значит в какую бы область мы не поставили пятую точку, не пересекая уже существующих рёбер мы можем соединить её только с тремя точками графа K₄. Что бы соединить её с четвёртой точкой нужно пересечь одно из рёбер.

Так в чём проблема, почему до сих пор эту задачу решают только перебором на компьютере? Или я что-то упустил и в задаче есть ещё какое-то условие?

[mihaild]

Недостаточно отсутствия 5 соприкасающихся областей. Возьмите два полных графа на 4 вершинах - ABCD и EFGH, возьмите дополнительно точку X, соедините XA, XB, XC, DE,DF, DG, XH, и попробуйте это раскрасить в четыре цвета.

[programer19]

хм, аргумент. Пошёл думать как бы переформулировать. Кстати Вы свой граф тоже распутать не сможете, как и K₅, а потому карты по такому графу не нарисовать :)

[mihaild]

programer19, было бы очень странно, если бы я сумел привести планарный граф, для которого 4х красок недостаточно:)