Изменения
Нет описания правки
Вершинной связностью графа называется
<tex> \varkappa (G) = \max \{ k | G </tex> вершинно <tex> k </tex> - связен <tex> \} </tex>. Полный граф <tex> \varkappa (K_n) = n - 1 </tex>.
{{Определение
Реберной связностью графа называется <tex> \lambda(G) = \max \{ l | G </tex> реберно <tex> l </tex> - связен <tex> \} </tex>
При <tex> n = 1, \lambda (K_1) = 0 </tex> .
{{Теорема
|statement= <tex> \varkappa (G) \leqslant \lambda (G) \leqslant \sigma (G) </tex> , где <tex> \sigma(G) </tex> - минимальная степень вершин графа <tex> G </tex>
|proof= smth<tex> \lambda (G) \leqslant \sigma (G) </tex> - очевидно. Рассмотрим граф <tex> \lambda (G) = l </tex>.Покажем, что можем удалить l вершин и сделать граф несвязным. Выберем вершину из правой компоненты.Тогда возможны варианты:1)Все <tex> l </tex> рёбер инцидентны вершине.Тогда: 1.1)Если вершина не единственна - удаляем вершину. 1.2)Если вершина единственная, тогда 1.2.1)Во второй компоненте <tex> l </tex> вершин - (??) 1.2.2)Удаляем её.2)Возьмем вершину во второй компоненте.Удалим у ребер, инцидентных с этими двумя вершинами, все левые концы, а у остальных - все правые концы.
}}
