---
tag: XAZ1R146FX
kind: statement
role: proposition
name: Graham–Pollak theorem
aliases: [alon-saks-seymour-conjecture]
sources:
  - wikipedia: en:64527577@r1375060215
    locator: Graham–Pollak theorem
    note: adopted
    mention: wikipedia://en/64527577
    sections: [Statement]
same_as:
  wikidata: Q97273070
  wikipedia: Graham–Pollak theorem
inventory: [69TQR87GAM]
---

## Statement

In graph theory, the **Graham–Pollak theorem** states that the edges of an $n$-vertex [[complete graph|03WKB2H474]] cannot be partitioned into fewer than $n-1$ [[complete bipartite graphs|0V0GC7BQAN]]. 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.