I dont understand Mengers Theorem (graph theory)

74 Views Asked by At

I looked for a good proof for Mengers Theorem and there was a good one on Wikipedia (https://en.wikipedia.org/wiki/Menger%27s_theorem) I understand the idea behind the proof but i stuck at some parts. As far what i understand: Its and induction over the edges. Its trivial if there are no edges.

  1. Why are we able to asume by induction that it also applies for $G-e$ and

  2. "If $G−e$ has a minimal $AB$-separator of size $k$, then there is an $AB$-connector of size $k$ in $G−e$, and hence in G. " ?

Now we define an $AB$-seperator S for $G-e$ with size less than k, otherwise it would be a better seperator for G. Now it tries to build those $S_1$ and $S_2$ according the image on wikipedia.

  1. Can someone explain me more detailed what happens from the point, where they define the $S_1$?

Thanks!