<p>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.  </p>

<p>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?</p>

CC BY-SA 3.0
2016-11-22T20:29:48.890Z
If you assume that $G$ is bipartite then the bound is tight you can consider $k$-regular graph.
Nikolai Karpov
CC BY-SA 3.0
2016-11-23T19:51:24.550Z
thanks! do you have a reference for this? is it from Bollobàs 'Random Graphs' book?
user1798883
<graph-theory><co.combinatorics><max-flow-min-cut><random-graphs>
expected number of edges for fixed min cut
user1798883
# expected number of edges for fixed min cut

(Asked by: username_0 on 2016-11-15)

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?

**Tags:** graph-theory, co.combinatorics, max-flow-min-cut, random-graphs
> **Comments:**
> **username_1**: If you assume that $G$ is bipartite then the bound is tight you can consider $k$-regular graph.  
> **username_0**: thanks! do you have a reference for this? is it from Bollobàs 'Random Graphs' book?  

---

## 0 answers

