Minimum multiway cuts in trees Original Research Article

We compare three lower bounds for the minimum cardinality of a multiway cut in a graph separating a given set Sof terminals. The main result is a relatively short algorithmic proof for a simplified version of a min-max theorem of the first and the third authors asserting that the best of the three lower bounds is actually attainable if every circuit of the graph contains a terminal node.