The transitive reduction of a binary relation on a set is the minimum relation on with the same transitive
closure as .
Thus
for any elements
and
of ,
provided that
and there exists no element of such that and .

The transitive reduction of a graph is the smallest graph such that , where is the transitive closure
of
(Skiena 1990, p. 203).