Задача по дискретной математике: докажите или опровергните — для любого простого неориентированного графа верно, что существует раскраска вершин в Δ+1 цветов, где Δ — максимальная степень графа; поясните связь с теоремой Брукса
Утверждение верно. Доказательство (жадный алгоритм). Пусть вершины графа \(G\) пронумерованы \(v_1,\dots,v_n\). Будем поочерёдно раскрашивать \(v_1\) по \(v_n\), для каждой вершины выбирая любой цвет из множества \(\{1,\dots,\Delta+1\}\), не совпадающий с цветами уже окрашенных соседей. В момент окраски вершина имеет не более \(\Delta\) соседей, а значит не более \(\Delta\) занятых цветов, поэтому среди \(\Delta+1\) цветов найдётся свободный. Получаем собственную раскраску не более чем в \(\Delta+1\) цветов. Связь с теоремой Брукса. Теорема Брукса говорит, что для связного простого графа \(G\), который не является полным графом \(K_{\Delta+1}\) и не является нечётным циклом \(C_{2k+1}\), выполняется более сильное неравенство \(\chi(G)\le\Delta\). Иначе говоря, общий тривиальный верхний предел \(\Delta+1\) укрепляется до \(\Delta\) за исключением двух семейств графов (полные графы и нечётные циклы), для которых оценка \(\Delta+1\) достигается.
Связь с теоремой Брукса. Теорема Брукса говорит, что для связного простого графа \(G\), который не является полным графом \(K_{\Delta+1}\) и не является нечётным циклом \(C_{2k+1}\), выполняется более сильное неравенство \(\chi(G)\le\Delta\). Иначе говоря, общий тривиальный верхний предел \(\Delta+1\) укрепляется до \(\Delta\) за исключением двух семейств графов (полные графы и нечётные циклы), для которых оценка \(\Delta+1\) достигается.