Находясь под впечатлением, какой я дурак, решил погуглить, оказалось, что на этом же форуме уже был пример рассуждений, аналогичных моим:
Есть ещё один чудик, некий Fayez A.Alhargan, так он вообще 4CT буквально в одну строку "решил". Пожалуй попробую кратко пересказать ход его мыслей.
Сначала он показывает, что если граф содержит подграф, изоморфный
![$K_n$ $K_n$](https://dxdy-02.korotkov.co.uk/f/9/6/b/96b697078d351b7b43bd5b5dce0254cd82.png)
с
![$n>4$ $n>4$](https://dxdy-03.korotkov.co.uk/f/e/0/0/e00bc4020b6d91cb9f80d0a2b8ca57f882.png)
, то все, приехали, четырьмя красками не обойтись (в принципе, это очевидно). Затем пытается доказать, что у планарного графа нет и быть не может такого слишком большого полного подграфа.
Делает он это примерно так. Пусть у графа есть
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
вершин,
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
ребер и
![$r$ $r$](https://dxdy-01.korotkov.co.uk/f/8/9/f/89f2e0d2d24bcf44db73aab8fc03252c82.png)
граней. Fayez замечает, что каждая страна на проблемной карте имеет как минимум три соседа, т.е., у каждой грани графа контурной карты (дуального графу соседства) имеется как минимум
три ребра, что с учетом соответствия каждого ребра куску границы между максимум
двумя странами приводит к неравенству
![$3r\leqslant 2m$ $3r\leqslant 2m$](https://dxdy-01.korotkov.co.uk/f/4/1/5/415ec73a064fa97a6c02d73e2cfdc2a082.png)
, которое вместе с формулой Эйлера
![$n-m+r=2$ $n-m+r=2$](https://dxdy-01.korotkov.co.uk/f/4/2/0/4200e02333eb81dbe4d3deb444c9173f82.png)
дает ещё одно неравенство
![$m\leqslant 3n-6$ $m\leqslant 3n-6$](https://dxdy-04.korotkov.co.uk/f/3/2/2/322c364c0ef02f598c690e03f00e593b82.png)
(это известный результат для планарных графов, популярное изложение см. например в А.Ю.Ольшанский, Плоские графы, СОЖ, №11, 96г.).
Теперь Fayez подставляет в это неравенство значение
![$m=m(n)$ $m=m(n)$](https://dxdy-04.korotkov.co.uk/f/f/1/2/f127763cd1332b50a49fa92ab63429e082.png)
для полного графа, которое может быть получено из комбинаторных соображений; именно, для
![$K_n$ $K_n$](https://dxdy-02.korotkov.co.uk/f/9/6/b/96b697078d351b7b43bd5b5dce0254cd82.png)
число
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
(количество ребер) равно
![$0,5(n^2-n)$ $0,5(n^2-n)$](https://dxdy-01.korotkov.co.uk/f/0/d/f/0df9dfb150f6e011d9e67a8e52ca7a1f82.png)
, т.е., количеству единиц над главной диагональю
![$n\times n$ $n\times n$](https://dxdy-03.korotkov.co.uk/f/2/b/e/2be744f3276b5219af5f8dd5f793e02c82.png)
матрицы забитой единицами. Подстановка в ранее полученную формулу дает квадратное неравенство
![$n^2-n\leqslant 6n-12$ $n^2-n\leqslant 6n-12$](https://dxdy-01.korotkov.co.uk/f/8/8/9/889ce0a310325e947dd2ee8b43d29bd282.png)
, которое имеет решение
![$n\in[3;\ 4]$ $n\in[3;\ 4]$](https://dxdy-04.korotkov.co.uk/f/3/4/7/347d0289472aa6325a062d56a3e8e99a82.png)
. Из этого результата сразу же и делается вывод о несуществовании у планарного графа более чем 4-вершинного полного подграфа (точнее говоря, вывод о неукладываемости
![$K_{>4}$ $K_{>4}$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a11c1a4de00d1a2175529f9154396f82.png)
, что почти тоже самое). :)
Хм, неужели действительно из последнего вывода следует 4-раскрашиваемость карты? Интуитивно, да, если потребовалась пятая краска при оптимальном раскрашивании полит. карты, значит текущая страна граничит с четырьмя другими, на которые уже растрачена 4-палитра, т.е, с четырьмя странами, граф соседсва для которых полный. Но ведь это не исключает существования какого-нибудь иного сценария неэкономичного использования красок... В общем, мне почему-то кажется, что здесь есть какая-то логическая проблема (типа импликации в одну сторону вместо эквивалентности)... Иначе, какого [вырезано] вокруг 4CT было столько шумихи и горы сгенерированной компьютером макулатуры? :)
Не я один такой, оказывается.
Это утешает.