Пусть [math]G(V,E)[/math] — связный неориентированный граф и [math]G[/math] не является [math]K_m[/math] или [math]C_{2m+1}[/math], ни для кого [math] m[/math], то [math]\chi(G) \le \Delta(G)[/math], где [math]\Delta(G)[/math] - максимальная степень вершин [math]G[/math] |
- Если [math] \Delta = 0[/math], [math] G = K_1[/math]
- Если [math] \Delta = 1[/math], [math] G = K_2[/math]
- Если [math] \Delta = 2[/math], то:
- [math] G [/math]— либо дерево либо четный цикл и тогда [math] \chi(G) = 2[/math]
- [math] G[/math] нечетный цикл
Поэтому мы будем считать до конца доказательства, что [math] \Delta(G) \ge 3[/math].
Если в [math]G[/math] существует вершина [math]v[/math] степени [math] deg\ v \lt \Delta(G)[/math], то по выше доказанной лемме [math] \chi(G) \le \Delta(G)[/math]. То есть осталось рассмотреть случай, когда [math]G[/math] — планарный граф.
- Если [math]G[/math] не является двусвязным графом, тогда в графе [math] G[/math] [math] \exists[/math] [math] v \in V[/math], где v — точка сочленения. Пусть [math]G_1,G_2[/math] две компоненты связности полученный при удалении вершины [math]v[/math].Тогда, по выше доказанной лемме [math]G_1,G_2[/math] можно правильно покрасить в [math]\Delta[/math] цветов.Поскольку количество соседей вершины [math] v [/math] в каждой из компонент не более [math] \Delta - 1[/math], то [math]G[/math] можно правильно раскрасить в [math]\Delta[/math] цветов.
- Если в графе [math] G[/math] [math] \exists[/math] [math] v,u \in V :(u,v) \notin E[/math] и при удалении вершин [math]v,u[/math] граф теряет связность .Пусть [math]G_1,G_2[/math] два подграфа [math] G:G_1 \cap G_2 = \{v,u\} \land G_1 \cup G_2 = G[/math]. Рассмотрим два случая:
- Если в одном из подграфов [math] G_1,G_2[/math] [math] deg\ u \lt \Delta - 2 [/math] или [math] deg\ v \lt \Delta - 2 [/math] то, подграфы [math]G_1,G_2[/math] можно правильно раскрасить в [math]\Delta[/math] цветов так, чтобы вершины [math] u,v [/math] были бы разных цветов.А из этого следует что, граф [math]G[/math] тоже можно правильно раскрасить в <\Delta> цветов.
- Если степени обоих вершин в одном из подграфов равны [math] \Delta - 1[/math] например в подграфе [math]G_1[/math]:
- [math] G_1,G_2 [/math] можно правильно раскрасить в [math]\Delta[/math] цветов так, чтобы вершины [math] u,v [/math] были бы разных цветов.Тогда очевидно, что оценка теоремы выполнена.
- [math]\exists p \in G_2: pu \in E \land pv \in E [/math], тогда мы можем правильно раскрасить [math]G_2[/math], где [math]deg\ u = deg\ v = 1[/math], в не более чем [math] \Delta [/math] цветов так, чтобы вершины [math]u,v[/math] были одного цвета.Следовательно,можно покрасить граф [math]G[/math] в не более чем [math]\Delta[/math] цветов.
- [math]\exists u_1,v_1 \in G_2: uu_1 \in E \land vv_1 \in E \land u_1 \neq v_1 [/math], тогда вместо вершин [math]\{u,v\}[/math] рассмотрим вершины [math]\{u,v_1\}[/math].Заметим, что при удалении этих вершин граф потеряет связность и между ними нет ребра,то есть для этой пары вершин можно провести рассуждения аналогичные тем которые проводились для вершин [math] v,u[/math], прямым образом вытекает, что граф [math] G[/math] можно правильно покрасить в не более чем [math]\Delta [/math] цветов.
- Если вышеописанные случаи не подходят, тогда рассмотрим [math]w \in V : deg\ w = \Delta[/math]. У вершины [math]w[/math] должны существовать две соседние вершины [math]u,v : uv \notin E [/math], в противном случаи [math]G = K_n[/math].Пусть [math]G_- = G - u - v [/math]. Заметим, что H связный граф, запустим на нем алгоритм bfs
|
