MathCastle
Graph TheorySuperchallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Superchallenge problem

A network has s,a,b,c,d,e,ts,a,b,c,d,e,t with links sa,sb,sc,ad,bd,be,ce,dt,et,ab,cdsa,sb,sc,ad,bd,be,ce,dt,et,ab,cd, and each of a,b,c,d,ea,b,c,d,e may be used by at most ONE path from ss to tt. What is the maximum number of internally vertex-disjoint paths from ss to tt?