Изменения
→Верхняя оценка длиной максимального нечетного цикла
|proof=
Опишем на графе следующий алгоритм раскраски:
*Из произвольной вершины <tex>v</tex> запусти запустим алгоритм поиска в глубину. Пусть <tex>T</tex> {{---}} дерево обхода глубина графа <tex>G</tex> с корнем в вершине <tex>v</tex>.
*Произвольную вершину <tex>u</tex>, покрасим в цвет <tex>dist(v,u)</tex> <tex> \bmod </tex> <tex> (\Delta + 1)</tex>, где <tex>dist(v,u)</tex>{{---}} расстояние между вершинами <tex>u,v</tex> в графe <tex>T</tex>.
Докажем от противного, что после выполнения описанного алгоритма граф <tex>G</tex> будет правильно раскрашен.
