Изменения

'''''Вершинной связностью''''' <mathtex>\varkappa</mathtex> графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу.

'''''Реберной связностью''''' <mathtex>\mathcal\lambda</mathtex> графа G называется наименьшее количество ребер, удаление которых приводит к несвязному или тривиальному графу.

<mathtex>\varkappa \le\mathcal\lambda \le \mathcal \delta </mathtex><ref><mathtex>\mathcal\delta</mathtex> - минимальная степень вершины графа G</ref>

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

Для любых натуральных чисел a, b, c, таких что a &le; b &le; c, существует граф G, у которого <mathtex>\varkappa = a, \lambda = b</mathtex> и <mathtex>\mathcal\delta = c </mathtex>.

Рассмотрим граф G, являющийся объединением двух полных графов <mathtex>G_1</mathtex> и <mathtex>G_2</mathtex>, содержащих c + 1 вершину. Отметим b вершин, принадлежащих подграфу <mathtex>G_1</mathtex> и a вершин, принадлежащих подграфу <mathtex>G_2</mathtex>. Добавим в граф G b ребер так, чтобы каждое ребро было инцидентно помеченной вершине, лежащей в подграфе <mathtex>G_1</mathtex> и помеченной вершине, лежащей в подграфе <mathtex>G_2</mathtex>, причем не осталось ни одной помеченной вершины, у которой не появилось хотя бы одно новое ребро, инцидентное ей.

1) Поскольку b &le; c, то было как минимум две непомеченные вершины, поэтому <mathtex> \mathcal \delta</mathtex> = с, так как минимальные степени вершин графов <mathtex>G_1</mathtex> и <mathtex>G_2</mathtex> была c, а степени их вершин не уменьшались.<br>2) Заметим, что между двумя вершинами графа G существует не меньше a вершинно-непересекающихся простых цепей, следовательно по [[теорема Менгера|теореме Менгера]] <mathtex>\varkappa </mathtex> &ge; a. Однако если удалить из графа G помеченные вершины его подграфа <mathtex>G_2</mathtex>, то граф G потеряет связность. Значит, <mathtex>\varkappa </mathtex> = a.<br>3) Аналогично рассуждению пункта 2, легко убедится, что <mathtex>\mathcal\lambda </mathtex> = b.