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, 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, write that all proofs are somehow based on linear algebra: "no combinatorial proof for this result is known". Construction of an optimal partition A partition into exactly complete bipartite graphs is easy to obtain: just order the vertices, and for each vertex except the last, form a star connecting it to all later vertices in the ordering. Other partitions are also possible. Proof of optimality The proof of the Graham–Pollak theorem described by (following ) defines a real variable for each vertex , where denotes the set of all vertices in the graph. Let the left sides and right sides of the th bipartite graph be denoted and , respectively and for any set of vertices define to be the sum of variables for vertices in : Then, in terms of this notation, the fact that the bipartite graphs partition the edges of the complete graph can be expressed as the equation Now consider the system of linear equations that sets and for each . Any solution to this system of equations would also obey the nonlinear equations But a sum of squares of real variables can only be zero if all the individual variables are zero, the trivial solution to the system of linear equations. If there were fewer than complete bipartite graphs, the system of equations would have fewer than equations in unknowns and would have a nontrivial solution, a contradiction. So the number of complete bipartite graphs must be at least . Related problems Distance labeling Graham and Pollak study a more general graph labeling problem, in which the vertices of a graph should be labeled with equal-length strings of the characters "0", "1", and "✶", in such a way that the distance between any two vertices equals the number of string positions where one vertex is labeled with a 0 and the other is labeled with a 1. A labeling like this with no "✶"