MathCastle
Graph TheoryHardWalks, Paths and Connectivity

Walks, Paths and Connectivity · Hard problem

A network has a source ss and a sink tt. From ss there are links to three relay points a,b,ca,b,c. Relays aa and bb both link onward to relay dd; relay cc links onward to relay ee. Finally dd and ee each link to tt. What is the maximum number of edge-disjoint paths from ss to tt?