Теорема Брукса - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:23:16Z

rollbackEdits.php mass rollback

185.220.101.186 в 05:06, 1 сентября 2022

2022-09-01T05:06:12Z

93.125.107.85: /* Теорема */

2019-12-17T21:19:45Z

‎Теорема

81.89.176.80: /* Теорема */

2018-12-25T19:00:17Z

‎Теорема

Lytr777: правки

2016-01-15T06:02:21Z

правки

Lytr777 в 05:15, 13 января 2016

2016-01-13T05:15:42Z

Dgerasimov: /* Вспомогательная Лемма */

2013-11-16T07:41:21Z

‎Вспомогательная Лемма

Danek g30 в 22:19, 19 января 2013

2013-01-19T22:19:53Z

Danek g30 в 22:18, 19 января 2013

2013-01-19T22:18:36Z

Danek g30 в 22:15, 19 января 2013

2013-01-19T22:15:27Z

← Предыдущая		Версия 16:23, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Вспомогательная лемма ==		== Вспомогательная лемма ==
	{{Лемма		{{Лемма

← Предыдущая		Версия 05:06, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Вспомогательная лемма ==		== Вспомогательная лемма ==
	{{Лемма		{{Лемма

@@ Строка 11: / Строка 11: @@
 {{Теорема
 |about= Брукса
-|statement=Пусть <tex>G(V,E)</tex> {{---}} связный неориентированный граф и <tex>G</tex> не является <tex>K_m</tex> или <tex>C_{2m+1}</tex>, ни для кого <tex> m</tex>, тогда <tex>\chi(G) \leqslant \Delta(G)</tex>, где <tex>\Delta(G)</tex> {{---}} максимальная степень вершин <tex>G</tex>
+|statement=Пусть <tex>G(V,E)</tex> {{---}} связный неориентированный граф и <tex>G</tex> не является <tex>K_m</tex> или <tex>C_{2m+1}</tex>, ни для какого <tex> m</tex>, тогда <tex>\chi(G) \leqslant \Delta(G)</tex>, где <tex>\Delta(G)</tex> {{---}} максимальная степень вершин <tex>G</tex>

@@ Строка 26: / Строка 26: @@
 ##Если <tex>G</tex> является вершинно двусвязным графом. Тогда, <tex> \exists</tex> <tex> v,u \in V :(u,v) \notin E</tex> и при удалении вершин <tex>v,u</tex> граф теряет связность. Пусть <tex>G_1,G_2</tex>  {{---}} два подграфа <tex> G:(G_1 \cap G_2 = \{v,u\})  \land (G_1 \cup G_2 = G)</tex>. Рассмотрим два случая.
 ### Если сумма степеней вершин <tex>u,v</tex> в каждом из подграфов <tex>G_1,G_2</tex> меньше <tex>2(\Delta-1)</tex>. Тогда, в одном из данных подграфах <tex> \deg u \leqslant \Delta - 2 </tex> или <tex> \deg v \leqslant \Delta - 2 </tex>. То есть, эти подграфы можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов. А из этого следует, что граф <tex>G</tex> тоже можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
-### Если сумма степеней вершин <tex>u,v</tex> в одном из подграфов <tex>G_1,G_2</tex> равна <tex>2(\Delta-1)</tex>. Тогда, степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex>, рассмотрим например, что в подграфе <tex>G_1</tex>:
+### Если сумма степеней вершин <tex>u,v</tex> в одном из подграфов <tex>G_1,G_2</tex> равна <tex>2(\Delta-1)</tex>. Тогда, степени обеих вершин в одном из подграфов равны <tex> \Delta - 1</tex>, рассмотрим например, что в подграфе <tex>G_1</tex>:
 ###* Если вершины <tex>u,v</tex> смежны с вершиной <tex>p \in G_2</tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где степени вершин <tex>u,v</tex> равны <tex>1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были  одного цвета. Следовательно, можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.
 ###*[[Файл:Brooks_2.png‎|400px|thumb|Алгоритм раскраски. Третий случай, пятый шаг]]Если вершины <tex>u,v</tex> смежны с вершинами <tex>u_1,v_1 \in G_2</tex> соответственно, тогда вместо вершин <tex>\{u,v\}</tex> рассмотрим вершины <tex>\{u,v_1\}</tex>. Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра. При этом, сумма степеней новой пары вершин в каждой из компонент, полученных после их удаления, меньше <tex>2(\Delta-1)</tex>. Поэтому, если для этой пары вершин  провести рассуждения аналогичные тем, которые проводились для вершин <tex> v,u</tex>, получится, что граф <tex> G</tex> можно правильно раскрасить в  не более чем <tex>\Delta </tex> цветов.

@@ Строка 1: / Строка 1: @@
 == Вспомогательная лемма ==
 {{Лемма
-|statement= Пусть <tex>G(V,E)</tex> {{---}} произвольный [[Отношение связности, компоненты связности|связный]] неориентированный граф и <tex>\Delta(G)</tex> {{---}} максимальная степень вершин <tex>G</tex>. Если в таком графе существует вершина <tex>w</tex> степени <tex> deg\ w < \Delta(G)</tex>, то <tex>\chi(G) \le \Delta(G)</tex>.
+|statement= Пусть <tex>G(V,E)</tex> {{---}} произвольный [[Отношение связности, компоненты связности|связный]] неориентированный граф и <tex>\Delta(G)</tex> {{---}} максимальная степень вершин <tex>G</tex>. Если в таком графе существует вершина <tex>w</tex> степени <tex> \deg w < \Delta(G)</tex>, то <tex>\chi(G) \leqslant \Delta(G)</tex>.
 |proof=
   [[Файл:Brooks_1.png‎|400px|thumb|Алгоритм раскраски на пятом шаге]]
-Запустим алгоритм [[Обход в ширину|обхода в ширину]] из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_n,</tex> где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>-ом шаге алгоритма bfs. Далее начнем красить вершины в обратном порядке в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. На <tex> i</tex>-ом шаге покраски, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей (т.к <tex> deg(v_{n - i+1}) \le \Delta(G)</tex> и предок данной вершины в дереве bfs еще не покрашен, а если предка нет, то это вершина и есть <tex>w</tex>), следовательно вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Поскольку на каждом шаге алгоритм отработает корректно, следовательно граф можно правильно раскрасить в не более чем <tex> \Delta</tex> цветов, то есть <tex> \chi(G) \le \Delta(G)</tex>.
+Запустим алгоритм [[Обход в ширину|обхода в ширину]] из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_n,</tex> где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>-ом шаге алгоритма bfs. Далее начнем красить вершины в обратном порядке в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. На <tex> i</tex>-ом шаге покраски, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей (т.к <tex> \deg(v_{n - i+1}) \leqslant \Delta(G)</tex> и предок данной вершины в дереве bfs еще не покрашен, а если предка нет, то это вершина и есть <tex>w</tex>), следовательно вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Поскольку на каждом шаге алгоритм отработает корректно, следовательно граф можно правильно раскрасить в не более чем <tex> \Delta</tex> цветов, то есть <tex> \chi(G) \leqslant \Delta(G)</tex>.
 }}
@@ Строка 11: / Строка 11: @@
 {{Теорема
 |about= Брукса
-|statement=Пусть <tex>G(V,E)</tex> {{---}} связный неориентированный граф и <tex>G</tex> не является <tex>K_m</tex> или <tex>C_{2m+1}</tex>, ни для кого <tex> m</tex>, тогда <tex>\chi(G) \le \Delta(G)</tex>, где <tex>\Delta(G)</tex> {{---}} максимальная степень вершин <tex>G</tex>
+|statement=Пусть <tex>G(V,E)</tex> {{---}} связный неориентированный граф и <tex>G</tex> не является <tex>K_m</tex> или <tex>C_{2m+1}</tex>, ни для кого <tex> m</tex>, тогда <tex>\chi(G) \leqslant \Delta(G)</tex>, где <tex>\Delta(G)</tex> {{---}} максимальная степень вершин <tex>G</tex>
 |proof=
 Для доказательства теоремы рассмотрим несколько случаев:
-#<tex>\Delta(G) \le 2</tex>, тогда:
+#<tex>\Delta(G) \leqslant 2</tex>, тогда:
 #*Если <tex> \Delta = 0</tex>, <tex> G = K_1</tex>
 #*Если <tex> \Delta = 1</tex>, <tex> G = K_2</tex>
 #*Если <tex> \Delta = 2</tex>, то:
-#*# <tex> G </tex>{{---}} либо дерево либо четный цикл и тогда <tex> \chi(G) = 2</tex>
+#*# <tex> G </tex> {{---}} либо дерево либо четный цикл и тогда <tex> \chi(G) = 2</tex>
 #*#<tex> G</tex> нечетный цикл
-#<tex>\Delta(G) \ge 3</tex>, тогда:
+#<tex>\Delta(G) \geqslant 3</tex>, тогда:
 ##Если <tex>G</tex> не является вершинно двусвязным графом, тогда в графе <tex> G</tex> <tex> \exists</tex> <tex> v \in V</tex> {{---}} [[Отношение связности, компоненты связности|точка сочленения]]. Пусть <tex>G_1,G_2</tex> {{---}} две компоненты связности, полученные при удалении вершины <tex>v</tex>. Тогда, по выше доказанной лемме эти компоненты можно правильно раскрасить в не более чем  <tex>\Delta</tex> цветов. Поскольку количество соседей вершины <tex> v </tex> в каждой из компонент не более <tex> \Delta - 1</tex>, то <tex>G</tex> можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
 ##Если <tex>G</tex> является вершинно двусвязным графом. Тогда, <tex> \exists</tex> <tex> v,u \in V :(u,v) \notin E</tex> и при удалении вершин <tex>v,u</tex> граф теряет связность. Пусть <tex>G_1,G_2</tex>  {{---}} два подграфа <tex> G:(G_1 \cap G_2 = \{v,u\})  \land (G_1 \cup G_2 = G)</tex>. Рассмотрим два случая.
-### Если сумма степеней вершин <tex>u,v</tex> в каждом из подграфов <tex>G_1,G_2</tex> меньше <tex>2(\Delta-1)</tex>. Тогда, в одном из данных подграфах <tex> deg\ u \le \Delta - 2 </tex> или <tex> deg\ v \le \Delta - 2 </tex>. То есть, эти подграфы можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов. А из этого следует, что граф <tex>G</tex> тоже можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
+### Если сумма степеней вершин <tex>u,v</tex> в каждом из подграфов <tex>G_1,G_2</tex> меньше <tex>2(\Delta-1)</tex>. Тогда, в одном из данных подграфах <tex> \deg u \leqslant \Delta - 2 </tex> или <tex> \deg v \leqslant \Delta - 2 </tex>. То есть, эти подграфы можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов. А из этого следует, что граф <tex>G</tex> тоже можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
 ### Если сумма степеней вершин <tex>u,v</tex> в одном из подграфов <tex>G_1,G_2</tex> равна <tex>2(\Delta-1)</tex>. Тогда, степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex>, рассмотрим например, что в подграфе <tex>G_1</tex>:
 ###* Если вершины <tex>u,v</tex> смежны с вершиной <tex>p \in G_2</tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где степени вершин <tex>u,v</tex> равны <tex>1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были  одного цвета. Следовательно, можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.
 ###*[[Файл:Brooks_2.png‎|400px|thumb|Алгоритм раскраски. Третий случай, пятый шаг]]Если вершины <tex>u,v</tex> смежны с вершинами <tex>u_1,v_1 \in G_2</tex> соответственно, тогда вместо вершин <tex>\{u,v\}</tex> рассмотрим вершины <tex>\{u,v_1\}</tex>. Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра. При этом, сумма степеней новой пары вершин в каждой из компонент, полученных после их удаления, меньше <tex>2(\Delta-1)</tex>. Поэтому, если для этой пары вершин  провести рассуждения аналогичные тем, которые проводились для вершин <tex> v,u</tex>, получится, что граф <tex> G</tex> можно правильно раскрасить в  не более чем <tex>\Delta </tex> цветов.
-##Если <tex>G</tex> является <tex>k</tex>-связным графом, где <tex>k > 2</tex>. Тогда, рассмотрим <tex>w \in V : deg\ w = \Delta</tex>. У вершины <tex>w</tex> должны существовать две соседние вершины <tex>u,v : uv \notin E </tex>, в противном случае <tex>G = K_n</tex>. Пусть <tex>G_- = G - u - v </tex>. Заметим, что <tex>G_-</tex> связный граф, запустим для <tex>G_-</tex> алгоритм  обхода в ширину из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_{n-2}</tex>, где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>-ом шаге алгоритма bfs. Теперь пусть <tex> v_{n-1} = v</tex>, и <tex>v_n = u</tex>. Покрасим <tex>v_n,v_{n-1}</tex> в один цвет, далее начнем красить вершины в обратном порядке, начиная с <tex>v_{n-2}</tex> в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. Заметим, что так всегда можно сделать, поскольку на <tex>i</tex>-ом шаге покраски, где <tex>i \neq n</tex>, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей. Следовательно, вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Вершину <tex>w</tex> мы тоже сможем правильно раскрасить в один из <tex>\Delta</tex> цветов потому, что ее <tex>\Delta</tex> соседей покрашено в не более чем <tex>\Delta - 1</tex> цветов. Таким образом граф <tex> G</tex> можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
+##Если <tex>G</tex> является <tex>k</tex>-связным графом, где <tex>k > 2</tex>. Тогда, рассмотрим <tex>w \in V : \deg w = \Delta</tex>. У вершины <tex>w</tex> должны существовать две соседние вершины <tex>u,v : uv \notin E </tex>, в противном случае <tex>G = K_n</tex>. Пусть <tex>G_- = G - u - v </tex>. Заметим, что <tex>G_-</tex> связный граф, запустим для <tex>G_-</tex> алгоритм  обхода в ширину из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_{n-2}</tex>, где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>-ом шаге алгоритма bfs. Теперь пусть <tex> v_{n-1} = v</tex>, и <tex>v_n = u</tex>. Покрасим <tex>v_n,v_{n-1}</tex> в один цвет, далее начнем красить вершины в обратном порядке, начиная с <tex>v_{n-2}</tex> в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. Заметим, что так всегда можно сделать, поскольку на <tex>i</tex>-ом шаге покраски, где <tex>i \neq n</tex>, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей. Следовательно, вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Вершину <tex>w</tex> мы тоже сможем правильно раскрасить в один из <tex>\Delta</tex> цветов потому, что ее <tex>\Delta</tex> соседей покрашено в не более чем <tex>\Delta - 1</tex> цветов. Таким образом граф <tex> G</tex> можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
 }}
@@ Строка 35: / Строка 35: @@
 *[[Раскраска графа]]
-== Источники ==
+== Источники информации ==
 *[http://myweb.facstaff.wwu.edu/sarkara/brooks.pdf Brooks’ Theorem]
 *[http://en.wikipedia.org/wiki/Brooks'_theorem Wikipedia: Brooks' theorem]

@@ Строка 24: / Строка 24: @@
 #<tex>\Delta(G) \ge 3</tex>, тогда:
 ##Если <tex>G</tex> не является вершинно двусвязным графом, тогда в графе <tex> G</tex> <tex> \exists</tex> <tex> v \in V</tex> {{---}} точка сочленения. Пусть <tex>G_1,G_2</tex> {{---}} две компоненты связности, полученные при удалении вершины <tex>v</tex>. Тогда, по выше доказанной лемме эти компоненты можно правильно раскрасить в не более чем  <tex>\Delta</tex> цветов. Поскольку количество соседей вершины <tex> v </tex> в каждой из компонент не более <tex> \Delta - 1</tex>, то <tex>G</tex> можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
-##Если <tex>G</tex> является вершинно двусвязным графом. Тогда, <tex> \exists</tex> <tex> v,u \in V :(u,v) \notin E</tex> и при удалении вершин <tex>v,u</tex> граф теряет связность . Пусть <tex>G_1,G_2</tex>  {{---}} два подграфа <tex> G:(G_1 \cap G_2 = \{v,u\})  \land (G_1 \cup G_2 = G)</tex>. Рассмотрим два случая.
+##Если <tex>G</tex> является вершинно двусвязным графом. Тогда, <tex> \exists</tex> <tex> v,u \in V :(u,v) \notin E</tex> и при удалении вершин <tex>v,u</tex> граф теряет связность. Пусть <tex>G_1,G_2</tex>  {{---}} два подграфа <tex> G:(G_1 \cap G_2 = \{v,u\})  \land (G_1 \cup G_2 = G)</tex>. Рассмотрим два случая.
 ### Если сумма степеней вершин <tex>u,v</tex> в каждом из подграфов <tex>G_1,G_2</tex> меньше <tex>2(\Delta-1)</tex>. Тогда, в одном из данных подграфах <tex> deg\ u \le \Delta - 2 </tex> или <tex> deg\ v \le \Delta - 2 </tex>. Тоесть, эти подграфы можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов так, чтобы вершины <tex> u,v </tex> были бы разных цветов. А из этого следует, что граф <tex>G</tex> тоже можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
-### Если сумма степеней вершин <tex>u,v</tex> в одном из подграфов <tex>G_1,G_2</tex> равна <tex>2(\Delta-1)</tex>. Тогда, степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex>, рассмотрим например,что в подграфе <tex>G_1</tex>:
+### Если сумма степеней вершин <tex>u,v</tex> в одном из подграфов <tex>G_1,G_2</tex> равна <tex>2(\Delta-1)</tex>. Тогда, степени обоих вершин в одном из подграфов равны <tex> \Delta - 1</tex>, рассмотрим например, что в подграфе <tex>G_1</tex>:
 ###* Если вершины <tex>u,v</tex> смежны с вершиной <tex>p \in G_2</tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где степени вершин <tex>u,v</tex> равны <tex>1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были  одного цвета. Следовательно, можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.
 ###*[[Файл:Brooks_2.png‎|400px|thumb|Алгоритм раскраски. Третий случай, пятый шаг]]Если вершины <tex>u,v</tex> смежны с вершинами <tex>u_1,v_1 \in G_2</tex> соответственно, тогда вместо вершин <tex>\{u,v\}</tex> рассмотрим вершины <tex>\{u,v_1\}</tex>. Заметим, что при удалении этих вершин граф потеряет связность, и между ними нет ребра. При этом, сумма степеней новой пары вершин в каждой из компонент, полученных после их удаления, меньше <tex>2(\Delta-1)</tex>. Поэтому, если для этой пары вершин  провести рассуждения аналогичные тем, которые проводились для вершин <tex> v,u</tex>, получится, что граф <tex> G</tex> можно правильно раскрасить в  не более чем <tex>\Delta </tex> цветов.

@@ Строка 29: / Строка 29: @@
 ###* Если вершины <tex>u,v</tex> смежны с вершиной <tex>p \in G_2</tex>, тогда мы можем правильно раскрасить <tex>G_2</tex>, где степени вершин <tex>u,v</tex> равны <tex>1</tex>, в не более чем <tex> \Delta </tex> цветов так, чтобы вершины <tex>u,v</tex> были  одного цвета. Следовательно, можно покрасить граф <tex>G</tex> в не более чем <tex>\Delta</tex> цветов.
 ###*[[Файл:Brooks_2.png‎|400px|thumb|Алгоритм раскраски. Третий случай, пятый шаг]]Если вершины <tex>u,v</tex> смежны с вершинами <tex>u_1,v_1 \in G_2</tex> соответственно, тогда вместо вершин <tex>\{u,v\}</tex> рассмотрим вершины <tex>\{u,v_1\}</tex>. Заметим, что при удалении этих вершин граф потеряет связность, и между ними нет ребра. При этом, сумма степеней новой пары вершин в каждой из компонент, полученных после их удаления, меньше <tex>2(\Delta-1)</tex>. Поэтому, если для этой пары вершин  провести рассуждения аналогичные тем, которые проводились для вершин <tex> v,u</tex>, получится, что граф <tex> G</tex> можно правильно раскрасить в  не более чем <tex>\Delta </tex> цветов.
-##Если <tex>G</tex> является <tex>k</tex>-связным графом, где <tex>k > 2</tex>. Тогда, рассмотрим <tex>w \in V : deg\ w = \Delta</tex>. У вершины <tex>w</tex> должны существовать две соседние вершины <tex>u,v : uv \notin E </tex>, в противном случае <tex>G = K_n</tex>. Пусть <tex>G_- = G - u - v </tex>. Заметим, что <tex>G_-</tex> связный граф, запустим для <tex>G_-</tex> алгоритм  обхода в ширину из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_{n-2}</tex>, где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>ом шаге алгоритма bfs. Теперь пусть <tex> v_{n-1} = v</tex>, и <tex>v_n = u</tex>. Покрасим <tex>v_n,v_{n-1}</tex> в один цвет, далее начнем красить вершины в обратном порядке, начиная с <tex>v_{n-2}</tex> в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. Заметим, что так всегда можно сделать, поскольку на <tex> i</tex>ом шаге покраски, где <tex>i \neq n</tex>, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей, следовательно, вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Вершину <tex>w</tex> мы тоже сможем правильно раскрасить в один из <tex>\Delta</tex> цветов потому, что ее <tex>\Delta</tex> соседей покрашено в не более чем <tex>\Delta - 1</tex> цветов. Таким образом граф <tex> G</tex> можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
+##Если <tex>G</tex> является <tex>k</tex>-связным графом, где <tex>k > 2</tex>. Тогда, рассмотрим <tex>w \in V : deg\ w = \Delta</tex>. У вершины <tex>w</tex> должны существовать две соседние вершины <tex>u,v : uv \notin E </tex>, в противном случае <tex>G = K_n</tex>. Пусть <tex>G_- = G - u - v </tex>. Заметим, что <tex>G_-</tex> связный граф, запустим для <tex>G_-</tex> алгоритм  обхода в ширину из вершины <tex>w</tex>. Пронумеруем вершины <tex>v_1,...,v_{n-2}</tex>, где <tex>v_i</tex> вершина рассмотренная на <tex>i</tex>ом шаге алгоритма bfs. Теперь пусть <tex> v_{n-1} = v</tex>, и <tex>v_n = u</tex>. Покрасим <tex>v_n,v_{n-1}</tex> в один цвет, далее начнем красить вершины в обратном порядке, начиная с <tex>v_{n-2}</tex> в один из <tex>\Delta</tex> цветов так, чтобы никакое ребро графа не соединяло вершины одного цвета. Заметим, что так всегда можно сделать, поскольку на <tex> i</tex>ом шаге покраски, где <tex>i \neq n</tex>, для вершины <tex> v_{n - i+1}</tex> есть не более <tex>\Delta(G) - 1</tex> уже покрашенных соседей. Следовательно, вершину <tex> v_{n-i+1}</tex> можно покрасить по крайней мере в один из свободных цветов. Вершину <tex>w</tex> мы тоже сможем правильно раскрасить в один из <tex>\Delta</tex> цветов потому, что ее <tex>\Delta</tex> соседей покрашено в не более чем <tex>\Delta - 1</tex> цветов. Таким образом граф <tex> G</tex> можно правильно раскрасить в  не более чем  <tex>\Delta</tex> цветов.
 }}