Woodall's conjecture

In the mathematics of directed graphs, Woodall's conjecture is an unproven relationship between dicuts and dijoins.

[2][1] It is a folklore result that the theorem is true for directed graphs whose minimum dicut has two edges.

[2] Any instance of the problem can be reduced to a directed acyclic graph by taking the condensation of the instance, a graph formed by contracting each strongly connected component to a single vertex.

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

[5][6][2] In the other direction, the Lucchesi–Younger theorem states that the minimum size of a dijoin equals the maximum number of disjoint dicuts that can be found in a given graph.

On the left, a dicut with the minimum number of edges for the given graph, that being 3 edges (in red), forming 2 partitions (the set of blue vertices, and the set of green). On the right, the same number of disjoint dijoins (each represented by a different color).