The Graham Pollak theorem is discussed at this link https://mathoverflow.net/questions/5449/combinatorial-results-without-known-combinatorial-proofs/5560#5560 .  I came up with a nice short and incomplete proof of it.  The tricky part for me was to realize it was incomplete.  Follow the commentary if you want to see my "D'oh" moment.
The induction started by taking an a,b complete bipartite subgraph of an (a+b) complete graph.

Gerhard "The Induction Looked So Pretty" Paseman, 2012.04.21