Не могу понять переход индукции (раскраска вершин графа)

[gogoshik]

Будьте любезны, объясните доказательство. Не понимаю шаг индукции.

Утверждение. Вершины любого плоского графа можно правильно раскрасить в $6$ цветов.

Доказательство (по индукции). Индукция по числу вершин.

База. $|V| = 1$ – очевидно.

Переход. $|V| > 1$. Так как граф планарный, то существует вершина $v \in V$ , такая что $deg(v) \leqslant 5$. (Это понятно. Есть такая лемма.)

По индукции $G \setminus v$ раскрашивается шестью цветами. (Вот это я не понимаю).

Пусть $c$ - способ окраски графа $G\setminus v$ шестью цветами. (И вот здесь я что-то не понимаю). Есть такой цвет, что ни одна из соседних вершин $v$ не окрашена им. Раскрасим вершину $v$ этим цветом.

[Someone]

gogoshik в сообщении #1343369 писал(а):

По индукции $G \setminus v$ раскрашивается шестью цветами. (Вот это я не понимаю).

Видимо, должно быть "По предположению индукции…"

Вы бы подробно доказательство написали. Так, как это полагается в доказательстве по индукции.

[gogoshik]

Извините, но у меня перед глазами только такой текст доказательства. Я хочу его преобразовать в более понятный (самому себе и может быть другим) вид. Я выделил места, где я испытываю трудности.

Предположение индукции. Пусть существует граф без одной вершины, в котором вершины раскрашиваются в 6 цветов.

С чего это вдруг?

[Geen]

gogoshik в сообщении #1343374 писал(а):

Пусть существует граф без одной вершины, в котором вершины раскрашиваются в 6 цветов.

Нет, предположение состоит в том, что любой граф планарный граф с $n$ вершинами раскрашивается в 6 цветов.

[gogoshik]

Почему то я запутываюсь. Не могу понять где.

Хорошо. Предположим, что любой планарный граф с $n$ вершинами раскрашивается в 6 цветов. Для графа с $n = 1$ это очевидно. Рассмотрим граф с $n + 1$ вершиной. В этом графе найдется вершина степени не более 5 (по лемме). Удалим эту вершину. Вершины, которые были смежны с удаленной вершиной раскрашиваются в 5 цветов. Добавим удаленную вершину и покрасим её в цвет, отличный от смежных вершин. Это будет шестой цвет.

Так верно?

[Geen]

gogoshik в сообщении #1343379 писал(а):

Так верно?

А что смущает? И чего не хватает?

[gogoshik]

Geen в сообщении #1343381 писал(а):

gogoshik в сообщении #1343379 писал(а):

Так верно?

А что смущает? И чего не хватает?

Я не знаю. Видимо не хватает квалификации. Я просто спросил, верен ли мой текст доказательства.

Особенно смущает хитрый неестественный трюк. Удалили вершину. Потом обратно её добавили. Я подсмотрел в исходном тексте. А так разве нормальный человек способен догадаться о таком фокусе.

[arseniiv]

Нормальный фокус, если это доказательство по индукции. Мы поделили все интересующие объекты на «уровни» (здесь — по числу вершин графа), индексированные натуральными числами, и показываем, что для всех объектов из каждого уровня утверждение верно. В индукционном переходе мы можем что-то сделать только выделением из объекта уровня $n+1$ каких-то объектов уровня $n$ и меньше, вот мы здесь и выделяем аккуратно выбранный подграф. Если же бы нам удалось не пользоваться подграфами, нам не нужно было бы трогать индукцию вообще.

-- Ср окт 03, 2018 02:50:41 --

gogoshik в сообщении #1343385 писал(а):

Потом обратно её добавили.

Зачем добавлять? Математические объекты неизменны. Мы рассмотрели подграф, исходный граф на это время никуда не делся.

-- Ср окт 03, 2018 02:51:50 --

Вот эта часть может быть понята неправильно, кстати:

gogoshik в сообщении #1343379 писал(а):

Вершины, которые были смежны с удаленной вершиной раскрашиваются в 5 цветов.

[gogoshik]

Спасибо за помощь. Только, когда мы работаем по индукции с графами и подграфами, то это не совсем обычно.

arseniiv в сообщении #1343386 писал(а):

Вот эта часть может быть понята неправильно

Почему?

[arseniiv]

Ну, как будто мы выделили подграф лишь из этих пяти и раскрасили. Это могут быть мои личные тараканы.

[gogoshik]

Может так будет лучше?

Предположим, что любой планарный граф с $n$ вершинами раскрашивается в 6 цветов. Для графа с $n = 1$ это очевидно. Рассмотрим граф с $n + 1$ вершиной. В этом графе найдется вершина степени не более 5 (по лемме). Удалим эту вершину со всеми выходящими из неё ребрами. После удаления получится плоский подграф в котором можно правильно раскрасить все вершины в 6 цветов (по предположению индукции). Причем вершины, которые были соседними с удаленной вершиной будут раскрашены. Так как их не более 5, то и использованных цветов будет не более 5. Добавим $n + 1$ вершину и покрасим её в цвет, которого нет среди цветов её соседей. Это будет шестой цвет.

[arseniiv]

gogoshik в сообщении #1343392 писал(а):

Предположим, что любой планарный граф с $n$ вершинами раскрашивается в 6 цветов.

Скорее, докажем. А то получается что-то странное. А так всё нормально.