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.