# Mean number of edges between two equal partitions

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.

• 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. – Jernej Dec 16 '12 at 10:23
• I'm not sure my thinking is correct I expected it to be sqrt(nk/2) or so – titus Dec 16 '12 at 10:38
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.