12.2.3. Теорема о пяти красках

ТЕОРЕМА Всякий планарный граф можно раскрасить пятью красками.

доказательство

Достаточно рассматривать связные графы, потому что

Индукция по р. База: если р ^ 5, то х ^ Р ^ 5. Пусть теорема верна для всех связных планарных графов с р вершинами. Рассмотрим граф G с р+ 1 вершиной. По третьему следствию к формуле Эйлера 3 v e V d(v) < 5. По индукционному предположению x(G — v) ^ 5. Нужно раскрасить вершину v.

Если d(v) < 5, то в 5-раскраске G - v существует цвет, свободный для v.

Если d(v) = 5 и для Г+(г>) использованы не все пять цветов, то в 5-раскраске G — v существует цвет, свободный для v.

Остался случай, когда d(v) = 5 и все пять цветов использоданы (вершина v_t покрашена в цвет г, рис. 12.2). Пусть Gi₃ — правильный подграф G - v, по­ рожденный всеми вершинами, покрашенными в цвета 1 или 3 в 5-раскраске графа G — v. Если vi и уз принадлежат разным компонентам связности гра­ фа gis, то в той компоненте, и которой находится v\, произведем перекраску1 «-»• 3. При этом получится 5-раскраска G - v, но цвет 1 будет свободен для v. В противном случае существует простая цепь, соединяющая vi и v₃ и состоя­ щая из вершин, покрашенных в цвета 1 и 3. В этом случае щ и v₄ принадлежат разным компонентам связности подграфа G₂₄ (так как граф G — планарный). Перекрасим вершины 2 -и- 4 в той компоненте связности графа G₂₄, которой принадлежит v₂, и получим 5-раскраску графа G-v, в которой цвет 2 свободен для v.

Рис. 12.2. Иллюстрация к доказательству теоремы о пяти красках