Dijoin

In a directed graph, a dijoin is a set of arcs covering every directed cut. For a positive integer k, a k-dijoin is a set of arcs containing k edges from every directed cut. A fundamental theorem about dijoins is the Lucchesi-Younger theorem on the minimum size of a dijoin.

The following observation (see e.g. Frank, Sebő and Tardos ) gives a useful property of inclusionwise minimal dijoins.

Lemma. Let D be a weakly connected digraph without cut arcs. If F is an inclusionwise minimal dijoin, then by reorienting the arcs of F we obtain a strongly connected digraph.