Let $D=(V,A)$ be a directed graph, with source $s$ and target $t$. Recall Menger's theorem ($M$):
"The maximum number of pairwise arrow-disjoint $s-t$ paths equals the minimal cardinality of an $s-t$ cut".
Apparently, this is equivalent to the statement ($M^\prime$):
"The maximum number of pairwise vertex-disjoint $s-t$ paths equals the minimal cardinality of an $s-t$ vertex-cut".
I am trying to read a proof of the fact that these two statements are equivalent, but I cannot seem to grasp a fundamental argument in the proof. It goes as follows.
$M\implies M^\prime$:
Let $D=(V,A)$ be a directed graph. Consider the directed graph $D^\prime=(V^\prime,A^\prime)$, which is constructed from $D$ by replacing each $v\in V$ by two vertices $v^\prime$ and $v^{\prime\prime}$ and drawing an arrow $(v^\prime,v^{\prime\prime}$, and by replacing each arrow $(u,v)\in A$ by an arrow $(u^{\prime\prime},v^\prime)$. This is fine. Now it simply states the following:
The maximum number of pairwise vertex-disjoint $s-t$ paths in $D$ equals the maximum number of pairwise arrow-disjoint $s^{\prime\prime}-t^\prime$ paths in $D^\prime$, and the minimal cardinality of an $s-t$ vertex-cut in $D$ equals the minimal cardinality of and $s^{\prime\prime}-t^\prime$ cut in $D^\prime$.
$M^\prime\implies M$:
Let $D=(V,A)$ be a directed graph. Consider the directed graph $D^\prime=(V^\prime,A^\prime)$, which is constructed by replacing each arrow $a=(u,v)\in A$ by a point $a$ and by connecting $u$ to $a$ and $a$ to $v$. Again, it is simply stated that:
The maximum number of pairwise arrow-disjoint $s-t$ paths in $D$ equals the maximum number of pairwise vertex-disjoint $s-t$ paths in $D^\prime$, and the minimal cardinality of an $s-t$ cut in $D$ equals the minimal cardinality of and $s-t$ vertex-cut in $D^\prime$.
I do not see/understand why the statements in bold are true. Of course, once you have those equalities, the proof follows. Could somebody explain to me why the statements in bold are true, or even better, prove them? It is much appreciated!
Let's take the first bold-typeface statement. All sets of vertex-disjoint paths in $D$ are arrow-disjoint too. These map directly to arrow-disjoint paths in $D'$, so we know that $\geq$ relation holds.
For $\leq$, consider a set of arrow-disjoint paths in $D'$ and a corresponding set of paths in $D$ (we yet do not know if it is vertex-disjoint or not). If a path $P$ from the latter set uses vertex $v$, then related path $P'$ in $D'$ uses arc $(v',v'')$. But because the former set is arrow-disjoint, no other path from the first set is allowed to use that arrow. This implies, that no other path in the second set uses vertex $v$ (and so indeed the second set contain paths that are vertex disjoint).
Similarly we prove the statement about cuts: any $s-t$ vertex cut in $D$ can be transformed to a $s''-t'$ cut in $D'$ by picking edges $(v',v'')$ for any $v$ in the cut. Also, any $s''-t'$ cut in $D'$ can be transformed into $s-t$ vertex cut by picking one incident vertex for each edge other than $s''$ or $t'$ (here we use the assumption that $s$ and $t$ are non-adjacent, otherwise there is no vertex cut in $D$ to speak of).
The other claim in bold typeface can be argued in the same way.
I hope this helps $\ddot\smile$
Edit: Added a paragraph about cuts.