Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 37 / 3 / c

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 areEach 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, givingFor 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$. ThereforeThe two certificates distinguish edge-disjoint paths from internally vertex-disjoint paths, exactly the distinction needed between the two failure models.