<p>An <span class="math-container">$r$</span>-regular expander should do it.</p>
<p>The following is a simple observation that I first saw in Li (arXiv:2106.05513): if an <span class="math-container">$r$</span>-regular graph has conductance <span class="math-container">$\phi$</span>, then the smaller side <span class="math-container">$S$</span> of a minimum cut contains at most <span class="math-container">$|S| \leq 1/\phi$</span> vertices. Indeed, by definition of conductance we have that <span class="math-container">$|E(S,S^c)| \geq \phi r |S|$</span>. Since this defines a minimum cut, <span class="math-container">$|E(S,S^c)| \leq r$</span> and hence <span class="math-container">$|S| \leq |E(S,S^c)|/(\phi r) \leq 1/\phi$</span>.</p>
<p>Assuming that <span class="math-container">$1/\phi &lt; r$</span> we see that the smaller side of a minimum cut can only contain <span class="math-container">$&lt;r$</span> vertices. Then notice that any set of <span class="math-container">$1&lt;\ell&lt;r$</span> vertices necessarily has cut value <span class="math-container">$&gt;r$</span>, which implies that the minimum cut must be a trivial cut.</p>

CC BY-SA 4.0
2021-06-18T05:43:53.997Z
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$
Karagounis Z
CC BY-SA 4.0
2021-06-18T06:00:35.237Z
E.g., [this note](http://snap.stanford.edu/class/cs224w-readings/ellis11expansion.pdf) shows that d-regular graphs have expansion $\geq 0.18$ for $d \geq 3$.
smapers
CC BY-SA 4.0
2021-06-18T06:10:44.010Z
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
Karagounis Z
CC BY-SA 4.0
2021-06-18T12:43:37.343Z
Alternatively look at [this post](https://lucatrevisan.wordpress.com/2016/04/21/cs294-expansion-of-random-graphs) 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.
smapers
CC BY-SA 4.0
2021-06-15T08:14:46.643Z
2021-06-15T08:14:46.643Z
smapers
<p>My question is: Given integers <span class="math-container">$r$</span> and <span class="math-container">$k$</span>, is there an <span class="math-container">$r$</span>-regular bipartite graph <span class="math-container">$G = L \cup R$</span> with <span class="math-container">$|L| = |R| = k$</span>, which is <span class="math-container">$r$</span>-edge connected, and such that every minimum cut is trivial?</p>
<p>We can make an <span class="math-container">$r$</span>-regular <span class="math-container">$r$</span>-edge connected bipartite graph <span class="math-container">$G = L \cup R$</span> with <span class="math-container">$|L| = |R| = k$</span>, 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).</p>
<p>If <span class="math-container">$r = 2$</span>, then I think the only <span class="math-container">$r$</span>-regular connected bipartite is a hamiltonian cycle, so it does not hold. But does it hold in <span class="math-container">$r &gt;2$</span>? I have also shown that all minimum cuts are trivial in complete bipartite graph <span class="math-container">$K_{r,r}$</span> (as long as <span class="math-container">$r \neq 2$</span>).</p>
<p>In general how can I ensure that the minimum cuts are trivial in a graph?</p>

<graph-theory><co.combinatorics><bipartite-graphs>
Is there a regular bipartite graph where the minimum cuts are trivial?
Karagounis Z
# Is there a regular bipartite graph where the minimum cuts are trivial?

(Asked by: username_0 on 2021-06-15)

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?

**Tags:** graph-theory, co.combinatorics, bipartite-graphs

---

## 1 answers

### Answer by username_1 on 2021-06-15. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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$  
> **username_1**: E.g., [this note](http://snap.stanford.edu/class/cs224w-readings/ellis11expansion.pdf) shows that d-regular graphs have expansion $\geq 0.18$ for $d \geq 3$.  
> **username_0**: 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  
> **username_1**: Alternatively look at [this post](https://lucatrevisan.wordpress.com/2016/04/21/cs294-expansion-of-random-graphs) 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.  

---

