Специальная математика. Соловьев А.Е. - 54 стр.

 Любой граф, содержащий в качестве подграфа граф гомеоморфный К5 или К3,3 или -
непланарен.
Теорема (Эйлера для планарных графов):
В любом планарном графе
 В + Г = Р + 2.
где: В - число вершин
     Г - число граней
     Р - число ребер
Доказательство:
                            1+1=0+2

                             2+1=1+2

                             3+2=3+2




                             4+2=4+2

Пусть есть граф с n вершинами, для которого это соотношение верно.
Добавление ребра приводит к увеличению на едитницу либо числа граней, либо вершин.

                              4.7. Задача о 4 красках

Это одна из самых знаменитых задач теории графов и математики вообще.
Достаточно ли четырех красок для раскраски любой политической карты мира так,
чтобы два государства, имеющие общую границу, были раскрашены в разные цвета?

В качестве иллюстрации можно взять произвольную "карту". Для облегчения анализа
представим государства в виде вершин графа. "Раскраску" отобразим цифрами.
Дуги будут говорить о наличии общих границ. Не должно быть дуг, соединяющих вершины
с одинаковыми цифрами.
                                         1          2         1

  1           2         1
                                                3
          3
  2
      1       1     4                    2          1       4
                                         1


Так что задачу можно переформулировать так:
Сколько необходимо красок в планарном графе, чтобы любые две смежные вершины были
раскрашены различными цветами?

Теорема: Трех красок мало.

              1
                  Пример доказывает, что 3-х красок мало
              4

                                       — 54 —