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

Лемма:

x, y вершины G, существует k вершинно непересекающихся пути из x в y. Тогда каждый из выбранных k путей будет иметь не более, чем одну точку пересечения с остальными путями.

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

[math]\triangleright[/math]

Пусть, существуют пути [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]

[math]\triangleleft[/math]

Теорема:

Пусть 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