Greedy clique decompositions and the Turán numbers (Q1896337)

A greedy \(p\)-clique decomposition is a decomposition of the edge set of a graph into cliques of order at least \(p\). At each step of this decomposition the edges of one maximal clique of order at least \(p\) are removed until none remain, then the remaining edges, one by one, are removed. Let \(G\) be a graph of order \(n\). It is shown that the sum of the orders of cliques in a greedy \(p\)-clique decomposition of \(G\) is at most twice the maximum number of edges in a graph of order \(n\) with no cliques of order \(p- 1\).