Graham–Pollak theorem

Statement

In graph theory, the Graham–Pollak theorem states that the edges of an $n$-vertex complete graph cannot be partitioned into fewer than $n-1$ complete bipartite graphs. It was first published by Ronald Graham and Henry O. Pollak in two papers in 1971 and 1972 (crediting Hans Witsenhausen for a key lemma), in connection with an application to telephone switching circuitry.