of and is a subset of , then is a module of , if and only if it is a module of . In (Gallai, 1967), Gallai defined the modular decomposition recursively on a graph with vertex set , as follows: As a base case, if only has one vertex, its modular decomposition is a single tree node. Gallai showed that if is connected and so is its complement, then the maximal modules that are proper subsets of are a partition of . They are therefore a modular partition. The quotient that they define is prime. The root of the tree is labeled a prime node, and these modules are assigned as children of . Since they are maximal, every module not represented so far is contained in a child of . For each child of , replacing with the modular decomposition tree of gives a representation of all modules of , by the key observation above. If is disconnected, its complement is connected. Every union of connected components is a module of . All other modules are subsets of a single connected component. This represents all modules, except for subsets of connected components. For each component , replacing by the modular decomposition tree of gives a representation of all modules of , by the key observation above. The root of the tree is labeled a parallel node, and it is attached in place of as a child of the root. The quotient defined by the children is the complement of a complete graph. If the complement of is disconnected, is connected. The subtrees that are children of are defined in a way that is symmetric with the case where is disconnected, since the modules of a graph are the same as the modules of its complement. The root of the tree is labeled a serial node, and the quotient defined by the children is a complete graph. The final tree has one-element sets of vertices of as its leaves, due to the base case. A set of vertices of is a module if and only if it is a node of the tree or a union of children of a series or parallel node. This implicitly gives all modular partitions of . It is in this sense that the modular decomposition tree "subsumes" all other ways of recursively decomposing into quotients. Algorithmic issues A data structure for representing the