Proof: Menger's Theorem | Graph Theory, Connectivity

We prove Menger's theorem stating that for two nonadjacent vertices u and v, the minimum number of vertices in a u-v separating set is equal to the maximum number of internally disjoint u-v paths.

If you want to learn about the theorem, see how it relates to vertex connectivity, and see an example of applying it before learning the proof, check out my lesson - Intro to Menger's Theorem:    • Intro to Menger's Theorem | Graph The...  

This proof of Menger's theorem is a proof by induction on the size of the graph, done in three cases. The first case is when there exists a minimum u-v separating set that contains a vertex adjacent to both u and v.

The second case is when there exists a minimum u-v separating set that contains a vertex not adjacent to u and a vertex not adjacent to v. The third case is when every minimum u-v separating set contains only neighbors of u that are not neighbors of v, or only neighbors of v that are not neighbors of u. I first read this proof in "A First Course in Graph Theory" by Chartrand and Zhang. This presentation is significantly due to their presentation of the proof.

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.

I strongly recommend this lesson if you're unsure about the idea of a "maximum number of internally disjoint paths". I think it can be a confusing concept, here is my lesson that touches on it:    • What are Vertex Disjoint Paths? | Gra...  

Lesson on vertex separating sets:    • What are Vertex Separating Sets? | Gr...  



I hope you find this video helpful, and be sure to ask any questions down in the comments!

********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.

Vallow Bandcamp: https://vallow.bandcamp.com/
Vallow Spotify: https://open.spotify.com/artist/0fRtu...
Vallow SoundCloud:   / benwatts-3  
********************************************************************

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Music Channel:    / seanemusic