Berge’s theorem for the maximum charge problem

In 1957 Berge [C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences 43 (1957) 842–844] established that a matching is maximum if and only if there are no augmenting paths in the graph. In this paper we prove Berge’s result for a generalization of the matching problem—the maximum charge problem with capacity constraints. We show that a charge is maximum if and only if there is no alternating path, or lasso, along which the charge can be augmented.