Menger's theorem tells us that for any two nonadjacent vertices, u and v, in a graph G, the minimum number of vertices in a u-v separating set is equal to the maximum number of internally disjoint u-v paths in G.
The Proof of Menger's Theorem: [ Ссылка ]
Remember that a u-v separating set S in a graph G is a set of vertices in G, distinct from u and v, such that u and v are disconnected in G - S. Then, a minimum u-v separating set is a u-v separating set of minimum cardinality.
Lesson on vertex connectivity: [ Ссылка ]
Here's my lesson on disjoint paths: [ Ссылка ]
Lesson on vertex separating sets: [ Ссылка ]
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: [ Ссылка ]
Follow Wrath of Math on...
● Instagram: [ Ссылка ]
● Facebook: [ Ссылка ]
● Twitter: [ Ссылка ]
My Music Channel: [ Ссылка ]
