Graham–Pollak theorem
From Wikipedia, the free encyclopedia
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.[1] 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.[2][3]
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.[4][5][6][7][8] More strongly, Aigner & Ziegler (2018) write that all proofs are somehow based on linear algebra: "no combinatorial proof for this result is known".[1]