Graham–Pollak theorem

A partition into exactly ${\displaystyle n-1}$ 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.[1] Other partitions are also possible.

The proof of the Graham–Pollak theorem described by Aigner & Ziegler (2018) (following Tverberg 1982) defines a real variable ${\displaystyle x_{i}}$ for each vertex ${\displaystyle v_{i}\in V}$, where ${\displaystyle V}$ denotes the set of all vertices in the graph. Let the left sides and right sides of the ${\displaystyle k}$th bipartite graph be denoted ${\displaystyle L_{k}}$ and ${\displaystyle R_{k}}$, respectively and for any set ${\displaystyle S}$ of vertices define ${\displaystyle X(S)}$ to be the sum of variables for vertices in ${\displaystyle S}$:

${\displaystyle X(S)=\sum _{v_{i}\in S}x_{i}.}$

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

${\displaystyle \sum _{i<j}x_{i}x_{j}=\sum _{k}X(L_{k})X(R_{k}).}$

Now consider the system of linear equations that sets ${\displaystyle X(V)=0}$ and ${\displaystyle X(L_{k})=0}$ for each ${\displaystyle k}$. Any solution to this system of equations would also obey the nonlinear equations

${\displaystyle {\begin{aligned}0&=X(V)^{2}={\Bigl (}\sum _{i}x_{i}{\Bigr )}^{2}\\&={\Bigl (}\sum _{i}x_{i}^{2}{\Bigr )}+{\Bigl (}2\sum _{i<j}x_{i}x_{j}{\Bigr )}\\&={\Bigl (}\sum _{i}x_{i}^{2}{\Bigr )}+{\Bigl (}2\sum _{k}X(L_{k})X(R_{k}){\Bigr )}\\&=\sum _{i}x_{i}^{2}.\\\end{aligned}}}$

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 ${\displaystyle n-1}$ complete bipartite graphs, the system of equations would have fewer than ${\displaystyle n}$ equations in ${\displaystyle n}$ unknowns and would have a nontrivial solution, a contradiction. So the number of complete bipartite graphs must be at least ${\displaystyle n-1}$.[1][4]