Изменения

Перейти к: навигация, поиск

K-связность

708 байт убрано, 01:04, 3 ноября 2011
Нет описания правки
|proof=
<tex> \lambda (G) \leqslant \sigma (G) </tex> - очевидно[[Вершинная, реберная связность, связь между ними и минимальной степенью вершины | См.статью по этой теме]]
Рассмотрим <tex> \varkappa (G) \leqslant \lambda (G) </tex>.
 
Пусть <tex> \lambda (G) = l </tex>.
Покажем, что можем удалить <tex> l </tex> вершин и сделать граф несвязным.
 
Выберем вершину из правой компоненты.Тогда возможны варианты:
 
1. Все <tex> l </tex> рёбер инцидентны вершине. Тогда:
 
# Если вершина не единственна - удаляем вершину.
# Если вершина единственная, тогда:
##Во второй компоненте более <tex> l - 1 </tex> вершин - удаляем их.
## Удаляем её.
 
2. Удалив не более <tex> l - 1 </tex> вершин получаем несвязный граф.
}}
Анонимный участник

Навигация