Graham-Pollak Theorem

There does not exist a partition of into complete bipartite graphs.

Proof

Suppose there is such a partition into for .
Let be the Adjacency Matrix of
with edges between to .
Then

where is the matrix with all s.
Let be the Adjacency Matrix when the edges in are directed
Note
Each has a rectangle block of s and the rest zeros.
Thus the rank of is .
Let .
Then has rank at most .
Since the matrix has rank ,
there is some such that .
Now calculate

which is a contradiction.