For a random undirected graph with $n$ nodes, where each node has $k$ incident edges ($nk/2$ edges in total), the vertex set is partitioned into two sets each having $n/2$ nodes.

What is the order of the number of edges that start in one partition and end in the other?

My back of the napkin calculation is half of total number of edges, $nk/4$. If I place randomly an edge it has $1/4$ chance of having both ends in one partition, $1/4$ chance of having both ends in the other partition and $1/2$ chance of having the ends in both. I find it surprising that it could be half.

  • $\begingroup$ what exactly is the question here? What you stated is correct and is oftentimes used to show that a graph has a mincut of at most that size. $\endgroup$
    – Jernej
    Commented Dec 16, 2012 at 10:23
  • $\begingroup$ I'm not sure my thinking is correct I expected it to be sqrt(nk/2) or so $\endgroup$
    – titus
    Commented Dec 16, 2012 at 10:38
  • $\begingroup$ Check if the answer ends your doubts about your reasoning. $\endgroup$
    – Jernej
    Commented Dec 16, 2012 at 10:42

1 Answer 1


Your thinking is correct. To verify your claim you can check this lecture notes on the probabilistic method by Matousek and Vondrak. More specifically check the proof of Theorem 3.3.1 stating that any graph with $m$ edges contains a bipartite subgraph with $\frac{m}{2}$ edges.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.