Теорема Брукса

Материал из Викиконспекты
Версия от 14:35, 25 декабря 2012; 188.134.48.37 (обсуждение) (Новая страница: «== Вспомогательные Леммы == {{Лемма |statement= Пусть <tex>G(V,E)</tex> - произвольный связный неориент...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

Лемма:
Пусть [math]G(V,E)[/math] - произвольный связный неориентированный граф и [math]\Delta(G)[/math] - максимальная степень вершин [math]G[/math]. Если в таком графе существует вершина [math]v[/math] степени [math] deg\ v \lt \Delta(G)[/math], то [math]\chi(G) \le \Delta(G)[/math].
Теорема:

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Брукса&oldid=28439»