In the mathematics of directed graphs, Woodall's conjecture is an unproven relationship between dicuts and dijoins. It was posed by Douglas Woodall in 1976.
A dicut is a partition of the vertices into two subsets such that all edges that cross the partition do so in the same direction. A dijoin is a subset of edges that, when contracted, produces a strongly connected graph; equivalently, it is a subset of edges that includes at least one edge from each dicut.
If the minimum number of edges in a dicut is
k
k
k
It is a folklore result that the theorem is true for directed graphs whose minimum dicut has two edges. 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. Another class of graphs for which the theorem has been proven true are the directed acyclic graphs in which every source vertex (a vertex without incoming edges) has a path to every sink vertex (a vertex without outgoing edges).
A fractional weighted version of the conjecture, posed by Jack Edmonds and Rick Giles, was refuted by Alexander Schrijver. 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.