Find maximum number of internally disjoint paths according to Menger's theorem.
Find maximum number of internally disjoint paths according to Menger's theorem.
In my calculation there are $6$ disjoint paths.
But I am not sure.
there are four options:
$(i) \ 3, \ (ii) \ 4, \ (iii) \ 5, \ (iv) \ 6$.
Help me
$\endgroup$1 Answer
$\begingroup$Assuming the number sought is the number of paths from $A$ to $B$, note that the edges partition into two sets not connected to each other except at $A$ and $B$. These two sets are isomorphic, and removing two vertices from each set (the second and fourth in each row of five vertices) disconnects $A$ from $B$; removing just one vertex does not cause a disconnection (as may be easily verified). Therefore the mininum vertex cut is $4$, which by Menger's theorem is the maximum number of internally disjoint paths from $A$ to $B$.
$\endgroup$
