Separability generalizes Dirac's theorem (Q1392561)

A set of vertices in a graph is a maximal clique module if it is a module (a homogeneous set) and a clique, and is inclusion-maximal with respect to both properties. A maximal clique module of a graph \(G\) is called a moplex if its neighborhood is a minimal separator of \(G\). A moplex is simplicial if its neighborhood is a clique. The authors prove: (1) Every incomplete (triangulated) graph has at least two nonadjacent (simplicial) moplexes. (2) On every graph, the lexicographic breadth-first-search ends at a vertex belonging to a moplex. Since in a triangulated graph every vertex of a moplex is a simplicial vertex, (1) generalizes a well-known theorem of \textit{G. A. Dirac} [On rigid circuit graphs, Abh. Math. Semin. Univ. Hamb. 25, 71-76 (1961)] saying that every incomplete triangulated graph has at least two nonadjacent simplicial vertices. (2) implies that a moplex in a graph can be found in linear time.