A maximal-clique partition of a graph is a family of its maximal complete sub-graphs that partitions its edge set. Many graphs do not have a maximal-clique partition, while some graphs have more than one. It is harder to find graphs in which maximal-clique partitions have different sizes. \(L(K_5)\) is a well-known example. In \(1982\), Pullman, Shank, and Wallis \([9]\) asked if there is a graph with fewer vertices than \(L(K_5)\) with this property. This paper confirms that there is no such graph.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.