Covering Cliques with Spanning Bicliques

The edges of the complete graph on n vertices can be covered by lg(n) spanning complete bipartite subgraphs. Here lg denotes the binary logarithm, and we round up to the nearest integer. However, the sum of the number of edges in these subgraphs is roughly lg(n)(n/2)2, while a cover consisting of n-1 spanning stars uses only (n-1)2 edges.

We show that the covering by spanning stars has the smallest total number of edges among all coverings of the clique by spanning bicliques, except when n is 4 or 8.