Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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
    
Check if the answer ends your doubts about your reasoning. –  Jernej Dec 16 '12 at 10:42
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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