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?


1 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.

  • $\begingroup$ 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$ $\endgroup$ Jun 18, 2021 at 5:43
  • $\begingroup$ E.g., this note shows that d-regular graphs have expansion $\geq 0.18$ for $d \geq 3$. $\endgroup$
    – smapers
    Jun 18, 2021 at 6:00
  • $\begingroup$ The note doesn't define h(G) or define 'expansion'. Is it the same as conductance? Also, it doesn't consider bipartite graphs, and I think it's plausible that those have significantly different connectivity properties $\endgroup$ Jun 18, 2021 at 6:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – smapers
    Jun 18, 2021 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.