Изменения

Пускай минимальная степень вершины графа <tex>G </tex> обозначается буквой <tex>\delta</tex>. Тогда:

Для любого графа <tex>G </tex> справедливо следующее неравенство:<br/><tex>\varkappa \le\lambda \le \delta </tex>

1) Проверим второе неравенство. Если в графе <tex>G </tex> нет ребер, то <tex> \lambda = 0 </tex>. Если ребра есть, то несвязный граф получаем из данного, удаляя все ребра, инцидентные вершине с наименьшей степенью. В любом случае <tex> \lambda \le \delta </tex>. <br/> 2) Чтобы проверить первое неравенство нужно рассмотреть несколько случаев. Если '''<tex>G''' </tex> - несвязный или тривиальный граф, то <tex> \varkappa = \lambda = 0 </tex>. Если <tex>G </tex> связен и имеет мост <tex>x</tex>, то <tex>\lambda = 1 </tex>. В последнем случае <tex> \varkappa = 1 </tex>, поскольку или граф <tex>G </tex> имеет точку сочленения, инцидентную ребру <tex>x</tex>, или же <tex>G = K<sub>2K_2</subtex>. Наконец, предположим, что граф <tex>G </tex> содержит множество из <tex> \lambda \ge 2 </tex> ребер, удаление которых делает его несвязным. Ясно, что удаляя <tex>\lambda - 1 </tex> ребер из этого множества получаем граф, имеющий мост <tex>x = uv</tex>. Для каждого из этих <tex>\lambda - 1 </tex> ребер выберем какую-либо инцидентную с ним вершину отличную от <tex>u </tex> и <tex>v</tex>. Удаление выбранных вершин приводит к удалению <tex>\lambda - 1 </tex> (а возможно, и большего числа) ребер. Если получаемый после такого удаления граф не связен, то <tex>\varkappa < \lambda </tex>; если же он связен, то в нем есть мост <tex>x</tex>, и поэтому удаление вершины <tex>u </tex> или ''<tex>v'' </tex> приводит либок несвязному, либо к тривиальному графу. в любом случае <tex> \varkappa \le \lambda</tex>.

Для любых натуральных чисел <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=[[Файл:LambdaKappaDeltaGraph.png|thumb|leftright|250x600px|Граф, в котором <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>, причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей.Тогда: <br> 1) Поскольку <tex>b &\le; c</tex>, то было как минимум две непомеченные вершины, поэтому <tex> \delta= c</tex> = с, так как минимальные степени вершин графов <tex>G_1</tex> и <tex>G_2</tex> была были равны <tex>c</tex>, а степени их вершин не уменьшались.<br> 2) Заметим, что между двумя вершинами графа <tex>G </tex> существует не меньше a вершинно-непересекающихся простых цепей, следовательно по [[теорема Менгера|теореме Менгера]] <tex>\varkappa \ge a</tex> &ge; a. Однако если удалить из графа <tex>G </tex> помеченные вершины его подграфа <tex>G_2</tex>, то граф <tex>G </tex> потеряет связность. Значит, <tex>\varkappa = a</tex> = a.<br> 3) Аналогично рассуждению пункта 2, легко убедится, что <tex>\lambda = b</tex> = b.