# Dijoin

From Egres Open

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 ^{[1]}) 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.

## References

- ↑ A. Frank, A. Sebő, É. Tardos,
*Covering directed and odd cuts*, Mathematical Programming Studies 22 (1984) 99-112. Journal link, Author link.