= Solution
Name the outer pentagon vertices, in order from the client clockwise, $c,T,R,B,L$. Name the upper inner vertex $U$, the left inner vertex $A$, and the lower-right inner vertex $D$. The two remaining inner vertices are the labelled servers $s_1,s_2$.
Four edge-disjoint server paths are
$$
c-A-s_1,\qquad c-U-s_2,\qquad c-T-R-B-D-s_2,\qquad c-L-A-U-D-s_1.
$$
Each uses different links, although some intermediary vertices are shared. Any three failed links therefore leave at least one path intact. The client has exactly four incident links; failing those four disconnects it. Thus the minimum link cut has size four, giving
$$
\boxed{k_{\max}=3.}
$$
For mixed failures use the three paths $c-A-s_1$, $c-U-s_2$ and $c-T-R-B-D-s_1$. Their internal vertices are disjoint, as are their links. One failed link or intermediary node can destroy at most one of these paths, so any two failures leave a path intact. Failing the three intermediary nodes $A,U,D$ disconnects both servers: $s_1$ has neighbors $A,D$, and $s_2$ has neighbors $U,D$. Therefore
$$
\boxed{m_{\max}=2.}
$$
The two certificates distinguish <edge-disjoint paths> from <internally vertex-disjoint paths>, exactly the distinction needed between the two failure models.
Back to article page
