MathCastle
Graph TheoryChallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Challenge problem

A network has s,a,b,c,d,ts,a,b,c,d,t with two-way links sa,sb,ac,bc,ad,bd,ct,dt,absa,sb,ac,bc,ad,bd,ct,dt,ab, and each of a,b,c,da,b,c,d may be used by at most ONE path from ss to tt (unlimited use at s,ts,t themselves). What is the maximum number of internally vertex-disjoint paths from ss to tt?