Dijoin

In mathematics, a dijoin is a subset of the edges of a directed graph, with the property that contracting every edge in the dijoin produces a strongly connected graph.

Woodall's conjecture, an unsolved problem in this area, states that in any directed graph the minimum number of edges in a dicut (the unweighted minimum closure) equals the maximum number of disjoint dijoins that can be found in the graph (a packing of dijoins).

[1][2] A fractional weighted version of the conjecture, posed by Jack Edmonds and Rick Giles, was refuted by Alexander Schrijver.

[3][4][1] The Lucchesi–Younger theorem states that the minimum size of a dijoin, in any given directed graph, equals the maximum number of disjoint dicuts that can be found in the graph.

[8] In planar graphs, dijoins and feedback arc sets are dual concepts.

When either the red set of edges or the green edge is contracted, the resulting graph is strongly connected. This means that each of these is a dijoin.