143
правки
Изменения
Доказательство вершинной
Пусть G - конечный, неориентированный граф, <math>\kappa(G) = k</math> <math>\Leftrightarrow</math> для всех пар вершин <math>x, y \backepsilon G</math> существует k вершинно непересекающихся путей из x в y
|proof=
Пусть, существует лишь <math>m < k</math> вершинно непересекающихся путей. Тогда все остальные пути будут пересекать эти m, причем с каждым из m все пересечения будут происходить в одной точке(если это не так, то можно было бы выбрать больше, чем m путей). Тогда удалив m точек пересечения (если с путем не пересекаются другие пути - то любую вершину) мы разорвем все пути из x в y. Однако, по условию необходимо удалить k вершин, чтобы граф потерял связность. Значит, предположение неверно. Прямое следствие доказано.
Докажем обратное:
Между x и y существует k вершинно неперескающихся путей, очевидно, нельзя удалить <math>m < k</math> вершин так, чтобы граф потерял связность. Покажем, что достаточно удалить k вершин, чтобы граф потерял связность. Возьмем все пути из x в y, они пересекут выбранные k, причем каждый из них в одной точке. Удалив точки пересечения мы порвем все пути. Теорема доказана.
}}
