Graham–Pollak theorem
In graph theory, the Graham–Pollak theorem states that the edges of an
[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".
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.
The proof of the Graham–Pollak theorem described by Aigner & Ziegler (2018) (following Tverberg 1982) defines a real variable
denotes the set of all vertices in the graph.
: 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
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.
complete bipartite graphs, the system of equations would have fewer than
unknowns and would have a nontrivial solution, a contradiction.
So the number of complete bipartite graphs must be at least
[1][4] 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 "✶" characters would give an isometric embedding into a hypercube, something that is only possible for graphs that are partial cubes, and in one of their papers Graham and Pollak call a labeling that allows "✶" characters an embedding into a "squashed cube".
[3] For each position of the label strings, one can define a complete bipartite graph in which one side of the bipartition consists of the vertices labeled with 0 in that position and the other side consists of the vertices labeled with 1, omitting the vertices labeled "✶".
In this way, a labeling of this type for the complete graph corresponds to a partition of its edges into complete bipartite graphs, with the lengths of the labels corresponding to the number of graphs in the partition.
[3] Noga Alon, Michael Saks, and Paul Seymour formulated a conjecture in the early 1990s that, if true, would significantly generalize the Graham–Pollak theorem: they conjectured that, whenever a graph of chromatic number
has its edges partitioned into complete bipartite subgraphs, at least
Equivalently, their conjecture states that edge-disjoint unions of
complete bipartite graphs can always be colored with at most
The conjecture was disproved by Huang and Sudakov in 2012, who constructed families of graphs formed as edge-disjoint unions of
complete bipartite graphs that require
[9] More strongly, the number of colors can be as large as
[10] The biclique partition problem takes as input an arbitrary undirected graph, and asks for a partition of its edges into a minimum number of complete bipartite graphs.
