Spanning circuit family

A spanning circuit family is a collection of directed cycles whose union contains every vertex of the directed graph. Different circuits may overlap. This is distinct from a cycle cover of a directed graph, which requires vertex-disjoint cycles.

For a nontrivial strongly connected directed graph, a coherent cyclic order of a digraph and the Dilworth theorem produce a spanning circuit family with at most its independence number circuits. Put a largest consecutive stable block first and duplicate its vertices as sinks. Use forward edges and edges into the sink copies to form an acyclic auxiliary graph. Its reachability order has width equal to the block size. Expand a chain partition to paths, then exchange intersecting path suffixes until the permutation of source-to-sink labels has as many cycles as possible. Paths in the same permutation cycle are disjoint, so identifying copied endpoints produces simple directed circuits. A windmill of directed triangles sharing one vertex shows that the bound is sharp.