MathCastle
Graph TheorySuperchallengeWalks, Paths and Connectivity

Walks, Paths and Connectivity · Superchallenge problem

A network has source 00 splitting into 44 links to 1,2,3,41,2,3,4; then 1,21,2 both link to a relay 55, and 3,43,4 both link to a relay 66; then 55 links to 7,87,8 and 66 links to 9,109,10; finally 7,8,9,107,8,9,10 all link to the sink 1111. Find the maximum number of pairwise EDGE-disjoint paths from 00 to 1111, minus the maximum number of pairwise internally VERTEX-disjoint paths from 00 to 1111.