On The Decomposition of Graphs Into Cliques

We show by an elementary argument that, given any greedy clique decomposition of a graph \(G\) with \(n\) vertices, the sum of the orders of the cliques is less than \(\frac{5}{8}n^2\). This gives support to a conjecture of Peter Winkler.