Is there a regular bipartite graph where the minimum cuts are trivial?

Question

My question is: Given integers $r$ and $k$, is there an $r$-regular bipartite graph $G = L \cup R$ with $|L| = |R| = k$, which is $r$-edge connected, and such that every minimum cut is trivial?

We can make an $r$-regular $r$-edge connected bipartite graph $G = L \cup R$ with $|L| = |R| = k$, by taking a union of some hamiltonian cycles, but it has many non-trivial minimum cuts. (I say a cut is trivial if it is the set of edges incident on a single vertex).

If $r = 2$, then I think the only $r$-regular connected bipartite is a hamiltonian cycle, so it does not hold. But does it hold in $r >2$? I have also shown that all minimum cuts are trivial in complete bipartite graph $K_{r,r}$ (as long as $r \neq 2$).

In general how can I ensure that the minimum cuts are trivial in a graph?

Answer 1

An $r$-regular expander should do it.

The following is a simple observation that I first saw in Li (arXiv:2106.05513): if an $r$-regular graph has conductance $\phi$, then the smaller side $S$ of a minimum cut contains at most $|S| \leq 1/\phi$ vertices. Indeed, by definition of conductance we have that $|E(S,S^c)| \geq \phi r |S|$. Since this defines a minimum cut, $|E(S,S^c)| \leq r$ and hence $|S| \leq |E(S,S^c)|/(\phi r) \leq 1/\phi$.

Assuming that $1/\phi < r$ we see that the smaller side of a minimum cut can only contain $<r$ vertices. Then notice that any set of $1<\ell<r$ vertices necessarily has cut value $>r$, which implies that the minimum cut must be a trivial cut.