Отметим справедливость следующих высказываний:
[[Теорема Менгера, альтернативное доказательство|''Теорема Менгера для вершинной <tex>k - </tex> связности'']] * Наименьшее число вершин, разделяющих две несмежные вершины <tex> u </tex> и <tex> v </tex>, равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих <tex> u </tex> и <tex> v </tex>. (См.[[Теорема Менгера, альтернативное доказательство|''Теорема Менгера для вершинной <tex>k - </tex> связности'']])
Тогда:
* {{Утверждение|statement=Граф <tex> G </tex> является '''вершинно <tex>k</tex> - вершинно связным ''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>k</tex> вершинно непересекающимися путями.}}
Подобные теоремы справедливы и для реберной связности. То есть:
Подобные теоремы справедливы * <tex>\lambda(G) = k</tex> <tex>\Leftrightarrow</tex> для всех пар вершин <tex> u </tex> и <tex> v </tex> существует <tex>k</tex> реберно непересекающихся путей из <tex> u </tex> в <tex> v </tex>. (См.[[Теорема Менгера, альтернативное доказательство|''Теорема Менгера для реберной <tex>k - </tex> связности. Тогда:'']])
* Граф <tex> G </tex> является '''<tex> l </tex> - реберно связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex> l </tex> - реберно непересекающимися путями.
Отсюда следует, что:
{{Утверждение
|statement=
Граф <tex> G </tex> является '''реберно <tex> l </tex> - связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex> l </tex> - реберно непересекающимися путями.
}}
==Смотри также==
