Изменения

<tex>k</tex>-cвязность {{- --}} одна из топологических характеристик графа.

Граф называется '''вершинно <tex>k</tex> - связным''', если удаление любых <tex> (k - 1) </tex> вершин оставляет граф связным.

<tex> \varkappa (G) = \max \{ k | G </tex> вершинно <tex> k </tex> - связен <tex> \} </tex>, при этом для полного графа полагаем <tex> \varkappa (K_n) = n - 1 </tex>.

Граф называется '''реберно <tex> l </tex> - связным''', если удаление любых <tex> (l - 1) </tex> ребер оставляет граф связным.

[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины|Реберной связностью]] графа называется <tex> \lambda(G) = \max \{ l | G </tex> реберно <tex> l </tex> - связен <tex> \} </tex>, для тривиального графа считаем <tex> \lambda (K_1) = 0 </tex>.

Пусть <tex> S </tex> {{- --}} множество вершин/ребер/вершин и ребер.

Из теоремы [[Теорема Менгера, альтернативное доказательство|теоремы Менгера для вершинной <tex>k - </tex> -связности]] имеем, что наименьшее число вершин, разделяющих две несмежные вершины <tex> u </tex> и <tex> v </tex>, равно наибольшему числу простых путей, не имеющих общих вершин, соединяющих <tex> u </tex> и <tex> v </tex>.

Граф <tex> G </tex> является '''вершинно <tex>k</tex> - связным ''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex>k</tex> вершинно непересекающимися путями.

Подобная теорема справедлива и для реберной связности. То есть из [[Теорема Менгера, альтернативное доказательство|''теоремы Менгера для реберной <tex>k - </tex> -связности'']] следует:

Граф  <tex> G </tex> является '''реберно <tex> l </tex> - связным''' <tex>\Leftrightarrow </tex> любая пара его вершин соединена по крайней мере <tex> l </tex> - реберно непересекающимися путями.