147
правок
Изменения
Нет описания правки
Для любого графа <tex>G</tex> справедливо следующее неравенство: <tex>\varkappa \le\lambda \le \delta </tex>
|proof=
[[Файл:K5Ver_ed_coh_1.png|thumb|right|150x150px180px|Полный граф. <tex> \lambda = \delta = \varkappa = 4</tex>]]
# Проверим второе неравенство. Если в графе <tex>G</tex> нет ребер, то <tex> \lambda = 0 </tex>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <tex> \lambda \le \delta </tex>.
# Чтобы проверить первое неравенство нужно рассмотреть несколько случаев.
|statement=
Для любых натуральных чисел <tex>a, b, c</tex>, таких что <tex>a \le b \le c</tex>, существует граф <tex>G</tex>, у которого <tex>\varkappa = a, \lambda = b</tex> и <tex>\delta = c </tex>
|proof=[[Файл:LambdaKappaDeltaGraphVer_ed_coh_2.png|thumb|right|250x600px300px|Граф, в котором <tex> \delta = 4</tex>, <tex>\lambda = 3</tex>, <tex>\varkappa = 2</tex>.]]
Рассмотрим граф <tex>G</tex>, являющийся объединением двух полных графов <tex>G_1</tex> и <tex>G_2</tex>, содержащих <tex>c + 1</tex> вершину. Отметим <tex>b</tex> вершин, принадлежащих подграфу <tex>G_1</tex> и <tex>a</tex> вершин, принадлежащих подграфу <tex>G_2</tex>. Добавим в граф <tex>G</tex> <tex>b</tex> ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в подграфе <tex>G_1</tex> и помеченной вершине, лежащей в подграфе <tex>G_2</tex>, причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей.
Тогда:
