A modular decomposition recursively partitions a graph into nonempty modules. A module is a vertex set whose vertices have the same neighbors outside the set. Between any two parts, either all possible edges are present or none are; a quotient graph records which parts are adjacent. Each part is decomposed recursively, with graphs on at most one vertex as the base case.

A decomposition has width at most $k$ if every substitution uses at most $k$ parts, except for disjoint unions and complete joins, whose numbers of parts are unrestricted. The quotient graphs need not be prime.