Find maximum number of internally disjoint paths according to Menger's theorem.

Question

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

Answer 1

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$.