I used this generator algorithm for DAGs (by Szabolcs):
{vertices, edges} = {7, 10};
elems = RandomSample@PadRight[ConstantArray[1, edges], vertices (vertices-1)/2];
adj = Take[FoldList[RotateLeft, elems, Range[0, vertices-2]], All,
vertices]~LowerTriangularize~-1;
g = AdjacencyGraph[adj, DirectedEdges -> True];
Removing redundant edges iteratively:
new = Graph[Flatten[If[GraphDistance[EdgeDelete[g, #], First@#,
Last@#] < Infinity, {}, #] & /@ EdgeList@g],
VertexLabels -> "Name", ImagePadding -> 10];
{HighlightGraph[g, new, VertexLabels -> "Name", ImagePadding -> 10], new}
For some graphs, the remaining graph is simply the path graph of the topologically sorted vertices:
