For a graph $G$, the bipartition number $\tau(G)$ is the minimum number of complete bipartite subgraphs whose edge sets partition the edge set of $G$. In 1971, Graham and Pollak proved that $\tau(K_n)=n-1$. Since then, there have been a number of short proofs for Graham-Pollak theorem by using linear algebra or by using matrix enumeration. We present a purely combinatorial proof for Graham-Pollak theorem. For a graph $G$ with $n$ vertices, one can show $\tau(G) \leq n- \alpha(G)$ easily, where $\alpha(G)$ is the independence number of $G$. Erd\H{o}s conjectured that almost all graphs $G$ satisfy $\tau(G)=n-\alpha(G)$. In this talk, we prove upper and lower bounds for $G(n,p)$ which gives support for Erd\H{o}s' conjecture. Joint work with Fan Chung.