Graham–Pollak theorem

Partition of the edges of the complete graph into five complete bipartite subgraphs: (light red), (light blue), (yellow), and two copies of (dark red and dark blue). According to the Graham–Pollak theorem, a partition into fewer than five complete bipartite subgraphs is not possible.

In graph theory, the Graham–Pollak theorem states that the edges of an -vertex complete graph cannot be partitioned into fewer than 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.

The theorem has since become well known and repeatedly studied and generalized in graph theory, in part because of its elegant proof using techniques from algebraic graph theory. More strongly, Aigner & Ziegler (2018) write that all proofs are somehow based on linear algebra: "no combinatorial proof for this result is known".