MathCastle
Graph TheoryChallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Challenge problem

A network of one-way cables joins s,a,b,c,m,x,d,e,f,ts,a,b,c,m,x,d,e,f,t: s→as\to a, s→bs\to b, s→cs\to c; a→ma\to m, b→mb\to m, c→mc\to m; m→xm\to x; x→dx\to d, x→ex\to e, x→fx\to f; d→td\to t, e→te\to t, f→tf\to t (every cable is usable only in the stated direction, and no cable has a stated capacity beyond 11). What is the minimum number of cables that must be cut to disconnect ss from tt?