In the mathematics of
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
s, the Lucchesi–Younger theorem is a relationship between
dicut
In mathematics, a dicut is a partition of the vertices of a directed graph into two subsets, so that each edge that has an endpoint in both subsets is directed from the first subset to the second. Each strongly connected component of the graph mu ...
s and
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. Equivalently, a dijoin is a subset of the edges that, for every dicut, inclu ...
s. It was published by Cláudio L. Lucchesi and Daniel H. Younger in 1978. Their proof resolved a conjecture that had been posed roughly a decade earlier by Younger, and in unpublished work by
Neil Robertson
Neil Robertson (born 11 February 1982) is an Australian professional snooker player who is a former world champion and former world number one. The only Australian to have won a ranking event, he is also the only player from outside the United ...
, motivated by the
duality in
planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
s between dijoins and
feedback arc set
In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks al ...
s.
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 a collection of dicuts are all disjoint, any dijoin must have at least one edge from each of these dicuts, and must have size at least equal to the size of the collection. Therefore, the maximum number of disjoint dicuts in any graph must be less than or equal to the minimum size of a dicut. The Lucchesi–Younger theorem states that this relation is always an equality. The minimum size of a dijoin equals the maximum number of disjoint dicuts that can be found in a given graph.
References
Directed graphs
{{DEFAULTSORT:Lucchesi-Younger theorem