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