![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/e/ef/Graham%25E2%2580%2593Pollak_partition.svg/640px-Graham%25E2%2580%2593Pollak_partition.svg.png&w=640&q=50)
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]
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ef/Graham%E2%80%93Pollak_partition.svg/320px-Graham%E2%80%93Pollak_partition.svg.png)
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]