Изменения
Фикс доказательств
{{Лемма
|statement=x, y вершины G, существует k вершинно непересекающихся пути из x в y. Тогда каждый все остальные пути пересекают выбранные k следующим образом:а) существуют вершины, принадлежащие первым k путям, такие, что любой новый путь проходит через одну из них.б) на каждом из выбранных k путей будет иметь не более, чем одну точку пересечения с остальными путями.одной такой вершины
|proof=
Пусть, существуют пути , не проходящие через одну из таких вершин <math>x, u_1 ...q...p... u_n, y</math>, <math>x, v_1 ...q... v_m, y</math> и <math>x, w_1 ...p... w_p, y</math> тогда последние 2 пути не пересекаются с первыми k, а по условию у нас всего k непересекающихся путей, а не <math>k + 1</math>
}}
Пусть G - конечный, неориентированный граф, <math>\kappa(G) = k</math> <math>\Leftrightarrow</math> для всех пар вершин <math>x, y \backepsilon G</math> существует k вершинно непересекающихся путей из x в y
|proof=
Пусть, существует лишь <math>m < k</math> вершинно непересекающихся путей. Тогда все остальные пути будут пересекать эти m, причем с каждым из по лемме можно удалить <math>l \le m все пересечения будут происходить в одной точке(если это не </math> вершин так, то можно было бы выбрать больше, чем m путей)чтобы разорвать все добавленные пути и l из выбранных изначально.. Тогда удалив m точек пересечения вершин (если с путем не пересекаются другие пути l и по одной из оставшихся <math>m - то любую вершинуl</math> путей) мы разорвем все пути из x в y. Однако, по условию необходимо удалить k вершин, чтобы граф потерял связность. Значит, предположение неверно. Прямое следствие доказано.
Докажем обратное:
Между x и y существует k вершинно неперескающихся путей, очевидно, нельзя удалить <math>m < k</math> вершин так, чтобы граф потерял связность. Покажем, что достаточно удалить k вершин, чтобы граф потерял связность. Возьмем все пути из x в y, они пересекут выбранные k, причем каждый из них в одной точкепо лемме можно выбрать не более k точек пересечения. Удалив точки все вершины пересечения и произвольные вершины из оставшихся путей (всего не более k) мы порвем все пути. Теорема доказана.
}}
Пусть G - конечный, неориентированный граф, <math>\lambda(G) = k</math> <math>\Leftrightarrow</math> для всех пар вершин <math>x, y \backepsilon G</math> существует k реберно непересекающихся путей из x в y
|proof=
}}
