# generate a graph with fixed min cut

Is there a constructive way to generate a graph with a fixed min cut equal to $k$? One approach is to generate a random graph and then try to make edges alterations (additions, deletions, swaps) to get the desired min cut -- but I am wondering if there is a more systematic procedure?

Ideally I would want to generate a random instance of a graph with min-cut=$k$, and I would want it to be bipartite, but insight on any part of this question would be helpful!

• Do you care about structure/the graph being different each time? Because you can just make the complete graph on $k$ vertices. Or if you want it bipartite, make the complete bipartite graph $K_{k,k}$. – Ryan Sep 27 '16 at 20:26
In his 1962 paper "The Maximum Connectivity of a Graph", Harary describes a way to construct for integers $p$ and $q$ with $q\ge p-1$ a way to construct a graph with $p$ vertices and $q$ edges that is $k=\lfloor 2q/p\rfloor$-connected. Roughly, the idea is to give indices from $0$ to $p-1$ to the $p$ vertices and then add edges between vertices whose indices (modulo $p$) differ by at most $k/2$ (the exact construction depends on whether or not $2q/p$ is an integer).