The Graham-Pollak Theorem states that the minimum number of complete bipartite graphs needed to disjointly cover the edge set of the complete graph on n vertices is n-1. The only known proofs all use linear algebra, and there os is no pure counting proof is known as far as I know. There is a chapter about this in Aigner and Ziegler's Proofs from the BOOK.
|
2 | fixed typo | ||
|
|
||||
|
|
1 | [made Community Wiki] | ||
|
The Graham-Pollak Theorem states that the minimum number of complete bipartite graphs needed to disjointly cover the edge set of the complete graph on n vertices is n-1. The only known proofs all use linear algebra, and there os no pure counting proof is known as far as I know. There is a chapter about this in Aigner and Ziegler's Proofs from the BOOK. |
||||
