A uniformly random $r$-regular bipartite graph on $n$ vertices is known to be $r$-edge connected. That is, with high probability as $n$ grows large, the minimum size of a cut in a random $r$-regular bipartite graph is $r$.


I was wondering if there is a similar statement for the following small extension: Is a uniformly random $(r+1,r)$-biregular bipartite graph almost surely $r$-edge connected?


An $(r+1,r)$-biregular bipartite graph is a bipartite graph where the left side vertices all have degree $r+1$, and the right side vertices have degree $r$.


It seems very reasonable that this extension is true since the graph has a higher density of edges than the $r$-regular case.


Thank you



Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?
The problem can be solved for $r\geq7$ by the following 2nd-eigenvalue results.


The first is from the paper [Edge-Disjoint Spanning Trees, Edge Connectivity, and Eigenvalues in Graphs](https://onlinelibrary.wiley.com/doi/abs/10.1002/jgt.21857).



> 
> Theorem 1.6. Let $k$ be an integer with $k \geq 2$ and $G$ be a graph with minimum degree $\delta \geq k$. If $\lambda\_2(G)<δ − 2(k−1)/(δ+1)$, then the edge connectivity of $G$ is at least $k$.
> 
> 
> 


In our case we have $\delta=k=r$, so we need $\lambda\_2(G) < r-2(r-1)/(r+1)$.


The second is from the paper [Spectral gap in random bipartite biregular graphs and applications](https://arxiv.org/abs/1804.07808).



> 
> **Theorem 4** (Spectral gap). Let $A$ be the adjacency matrix of a bipartite, biregular random graph uniformly sampled from all biregular graphs with $n$ and $m$ vertices for each part and degrees $d\_1$, $d\_2$. Without loss of generality, assume $d\_1 \geq d\_2$ or, equivalently, $n \leq m$.
> Then:
> (i) Its second largest eigenvalue $\lambda\_2(A)$ satisfies $\lambda\_2(A) \leq \sqrt{d\_1-1}+\sqrt{d\_2-1} + \epsilon\_n'$ a.a.s with $\epsilon\_n' \rightarrow 0$ as $n \rightarrow \infty$.
> 
> 
> 


Here we have $d\_1=r+1$ and $d\_2=r$, so we have $\lambda\_2(A) \leq \sqrt{r}+\sqrt{r-1}+\epsilon\_n'$ a.a.s. This bound guarantees $r$-edge-connectivity when $r \geq 7$.


