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

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?

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 $$ vertices. Then notice that any set of $$1<\ell vertices necessarily has cut value $$>r$$, which implies that the minimum cut must be a trivial cut.
• That is helpful, thank you. I'm not too familiar with expanders, is there a reference that proves the existence of bipartite, r-regular expander graphs with conductance at least 1/r? This also might help me understand what part of this proof breaks down when $r=2$ Jun 18, 2021 at 5:43
• E.g., this note shows that d-regular graphs have expansion $\geq 0.18$ for $d \geq 3$. Jun 18, 2021 at 6:00
• Alternatively look at this post by Trevisan. It is explicitly shown that w.h.p., $\phi \geq 1/108$ if $d = 18$. Better bounds are possible, but sometimes hidden in the literature. Jun 18, 2021 at 12:43