Теорема Менгера

Теорема:

Пусть G - конечный, неориентированный граф, [math]\kappa(G) = k[/math] [math]\Leftrightarrow[/math] для всех пар вершин [math]x, y \backepsilon G[/math] существует k вершинно непересекающихся путей из x в y

Доказательство:

[math]\triangleright[/math]

Пусть, существует лишь [math]m \lt k[/math] вершинно непересекающихся путей. Тогда все остальные пути будут пересекать эти m, причем с каждым из m все пересечения будут происходить в одной точке(если это не так, то можно было бы выбрать больше, чем m путей). Тогда удалив m точек пересечения (если с путем не пересекаются другие пути - то любую вершину) мы разорвем все пути из x в y. Однако, по условию необходимо удалить k вершин, чтобы граф потерял связность. Значит, предположение неверно. Прямое следствие доказано. Докажем обратное: Между x и y существует k вершинно неперескающихся путей, очевидно, нельзя удалить [math]m \lt k[/math] вершин так, чтобы граф потерял связность. Покажем, что достаточно удалить k вершин, чтобы граф потерял связность. Возьмем все пути из x в y, они пересекут выбранные k, причем каждый из них в одной точке. Удалив точки пересечения мы порвем все пути. Теорема доказана.

[math]\triangleleft[/math]

Теорема:

Пусть G - конечный, неориентированный граф, [math]\lambda(G) = k[/math] [math]\Leftrightarrow[/math] для всех пар вершин [math]x, y \backepsilon G[/math] существует k реберно непересекающихся путей из x в y