Теорема Брукса
В лаборатории Че проходит семинарам по доказательствам из Книги, как вошедшим в книгу Айгнера-Циглера, так и не вошедшим. Вчера Глеб Ненашев рассказал свою версию доказательства Ловаса теоремы Брукса, которого я раньше не знал.
Итак, докажем, что если в связном графе G степени всех вершин не превосходят d>2 и G не есть полный граф на d+1 вершине, то вершины G можно правильно покрасить в d цветов.
Начнем с нескольких простых наблюдений.
1) Если граф H нельзя покрасить в k цветов, то он содержит индуцированный подграф, в котором степени вершин не меньше k (то есть можно выкинуть из него несколько вершин так, что степени оставшихся будут не меньше k). Доказательство: если степень вершины v меньше k, то граф H-v также нельзя покрасить в k цветов (иначе покрасим его, а потом докрасим v). Удалим вершину v и продолжим процесс, в итоге останется подграф, в котором все степени не меньше k.
2) Пусть u,v --- две несмежные вершины графа H. Рассмотрим графы H/uv, в котором вершины u,v склеены в одну (кратные ребра после склеивания сразу делаем простыми), и граф H+uv, в котором добавлено ребро uv. Граф H можно покрасить в k цветов если и только если хотя бы один из этих двух графов можно. Доказательство: покраскам H, в которых вершины u и v одного цвета, соответствуют покраски H/uv, а тем, в которых u и v разного цвета, покраски H+uv. Рекурсия H->(H/uv,H+uv) вообще играет важную роль в теории графов, не только хроматической.
Перейдем к доказательству теоремы Брукса. Будем считать, что для графов с меньшим числом вершин, чем у G, утверждение теоремы Брукса выполняется, а для графа G нет. Тогда степени всех вершин графа G равны d, потому что согласно 1) в G есть подграф с таким свойством, а из-за связности он обязан совпадать с G.
Рассмотрим любую вершину p графа G, у нее найдутся два несмежных соседа u,v. Рассмотрим граф G/uv. По 2) его не покрасить в d цветов. Этот граф связен, и степени всех его вершин, кроме, возможно, вершины z, получаемой отождествлением u и v, не превосходят d. Кроме того, степень вершины p строго меньше, чем d. Следовательно, в нем по 1) найдется индуцированный подграф H, в котором степени всех вершин не меньше d. Этот подграф непременно содержит вершину z, потому что степени оставшихся и так были не больше d, а из-за связности мы должны были удалить какие-то ведущие в них ребра. Таким образом, в графе H есть вершина z и несколько вершин степени d, которые не смежны, таким образом, с вершинами вне H.
Попробуем теперь покрасить граф G+uv. Он состоит из графа H', стягиванием ребра uv в котором служит граф H, и графа H~, состоящего из вершин u,v и вершин, не входящих в H'. Эти два графа имеют общее ребро uv, а их вершины, отличные от u и v, не смежны. Таким образом, если мы покрасим каждый из них d цветов, то склеивая эти раскраски по ребру uv (можно считать, что вершины u,v покрашены оба раза в белый и голубой цвета соответственно) получим раскраску графа G+uv. Заметим, что степени всех вершин графов H', H~ не превосходят d. В самом деле, для всех вершин, кроме u,v это очевидно, и проверить следует лишь что, например, вершина u, имеющая степень d+1 в графе G+uv, соединена не только с вершинами H' или не только с вершинами H~. Первое ясно: вершина u соединена с вершиной p, лежащей в H~. Если же она соединена только с вершинами H~, то в графе H степень вершины z будет строго меньше d (ребрам, выходящим в графе H из z, будут соответствовать лишь ребра, выходящие в G из v, причем не все --- например, не ребро zp). Таким образом, для графов H', H~ (оба имеют меньше вершин, чем G) выполняется утверждение теоремы Брукса, так что один из них должен быть полным графом на d+1 вершине. Это может быть только граф H~, поскольку в графе H' вершины u,v не имеют общих соседей (такой общий сосед имел бы степень меньше d в графе H и потому попал бы в H~). В этом случае степень вершины z в графе H получается не больше, чем 2 --- противоречие.
Итак, докажем, что если в связном графе G степени всех вершин не превосходят d>2 и G не есть полный граф на d+1 вершине, то вершины G можно правильно покрасить в d цветов.
Начнем с нескольких простых наблюдений.
1) Если граф H нельзя покрасить в k цветов, то он содержит индуцированный подграф, в котором степени вершин не меньше k (то есть можно выкинуть из него несколько вершин так, что степени оставшихся будут не меньше k). Доказательство: если степень вершины v меньше k, то граф H-v также нельзя покрасить в k цветов (иначе покрасим его, а потом докрасим v). Удалим вершину v и продолжим процесс, в итоге останется подграф, в котором все степени не меньше k.
2) Пусть u,v --- две несмежные вершины графа H. Рассмотрим графы H/uv, в котором вершины u,v склеены в одну (кратные ребра после склеивания сразу делаем простыми), и граф H+uv, в котором добавлено ребро uv. Граф H можно покрасить в k цветов если и только если хотя бы один из этих двух графов можно. Доказательство: покраскам H, в которых вершины u и v одного цвета, соответствуют покраски H/uv, а тем, в которых u и v разного цвета, покраски H+uv. Рекурсия H->(H/uv,H+uv) вообще играет важную роль в теории графов, не только хроматической.
Перейдем к доказательству теоремы Брукса. Будем считать, что для графов с меньшим числом вершин, чем у G, утверждение теоремы Брукса выполняется, а для графа G нет. Тогда степени всех вершин графа G равны d, потому что согласно 1) в G есть подграф с таким свойством, а из-за связности он обязан совпадать с G.
Рассмотрим любую вершину p графа G, у нее найдутся два несмежных соседа u,v. Рассмотрим граф G/uv. По 2) его не покрасить в d цветов. Этот граф связен, и степени всех его вершин, кроме, возможно, вершины z, получаемой отождествлением u и v, не превосходят d. Кроме того, степень вершины p строго меньше, чем d. Следовательно, в нем по 1) найдется индуцированный подграф H, в котором степени всех вершин не меньше d. Этот подграф непременно содержит вершину z, потому что степени оставшихся и так были не больше d, а из-за связности мы должны были удалить какие-то ведущие в них ребра. Таким образом, в графе H есть вершина z и несколько вершин степени d, которые не смежны, таким образом, с вершинами вне H.
Попробуем теперь покрасить граф G+uv. Он состоит из графа H', стягиванием ребра uv в котором служит граф H, и графа H~, состоящего из вершин u,v и вершин, не входящих в H'. Эти два графа имеют общее ребро uv, а их вершины, отличные от u и v, не смежны. Таким образом, если мы покрасим каждый из них d цветов, то склеивая эти раскраски по ребру uv (можно считать, что вершины u,v покрашены оба раза в белый и голубой цвета соответственно) получим раскраску графа G+uv. Заметим, что степени всех вершин графов H', H~ не превосходят d. В самом деле, для всех вершин, кроме u,v это очевидно, и проверить следует лишь что, например, вершина u, имеющая степень d+1 в графе G+uv, соединена не только с вершинами H' или не только с вершинами H~. Первое ясно: вершина u соединена с вершиной p, лежащей в H~. Если же она соединена только с вершинами H~, то в графе H степень вершины z будет строго меньше d (ребрам, выходящим в графе H из z, будут соответствовать лишь ребра, выходящие в G из v, причем не все --- например, не ребро zp). Таким образом, для графов H', H~ (оба имеют меньше вершин, чем G) выполняется утверждение теоремы Брукса, так что один из них должен быть полным графом на d+1 вершине. Это может быть только граф H~, поскольку в графе H' вершины u,v не имеют общих соседей (такой общий сосед имел бы степень меньше d в графе H и потому попал бы в H~). В этом случае степень вершины z в графе H получается не больше, чем 2 --- противоречие.