Crossing Properties of Multiterminal Cuts

Gomory and Hu proved the following classical result: For any graph with nonnegative edge weights, there exists a collection of noncrossing cuts that contains a minimum cut for every pair of nodes. In this paper, we show how this result generalizes for a natural multiterminal cut problem. We also show that our result is "best possible," for k = 3, by using a computer to find feasible solutions to several large systems of linear inequalities. © 1999 John Wiley & Sons, Inc. Networks 34: 215-220, 1999