It is known that a graph $G=(V,E)$ with $n$ nodes and min cut $k$, must have at least $\frac{1}{2}nk$ edges.

Are there any tighter bounds or expectations I can place on $|E|$ if I assume that $G$ follows a particular random graph model? Or if it is bipartite?

  • $\begingroup$ If you assume that $G$ is bipartite then the bound is tight you can consider $k$-regular graph. $\endgroup$ Nov 22 '16 at 20:29
  • $\begingroup$ thanks! do you have a reference for this? is it from Bollobàs 'Random Graphs' book? $\endgroup$ Nov 23 '16 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.