Directed Cut

A directed cut in a directed graph is the set of directed edges from one part to the other part of a set partition of the vertex set into two parts. Write for the number of these directed edges. In contrast to an undirected cut, and can differ (Folz and Tyomkyn 2026).

Folz and Tyomkyn (2026) proved that, for every fixed integer and sufficiently large , every loopless directed graph with directed edges, no repeated ordered edges, and minimum outdegree at least has a set partition of its vertex set into two parts satisfying

where is the ceiling function. Oppositely directed edges are allowed. The bound is sharp for infinitely many . For , the weaker bound holds for every . Folz and Tyomkyn (2026) report that LLMs obtained the proofs with human input, that the authors revised them, and that they were verified in Lean.