Is a random $(r+1,r)$-biregular bipartite graph $r$-edge connected w.h.p?

Question

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

Answer 1

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.

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.

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