# expected number of edges for fixed min cut

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?

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