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

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

• I think it may help if you give complete definitions of the notions used in this post: $n$, "uniformly random", "$(r+1,r)$-biregular bipartite graph", "$r$-edge connected", "a cut", etc., as well as a reference to the proof of the fact that "A uniformly random $r$-regular bipartite graph is [...] $r$-edge connected." Jan 2, 2022 at 20:57
• I clarified some of the terminology. The result on the connectivity of random $r$-regular graphs is stated on this wikipedia article with references to the proofs en.wikipedia.org/wiki/Random_regular_graph#cite_note-2 Jan 2, 2022 at 22:52

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

• Thank you, this is very helpful. There is clearly a lot of literature on this topic which I am not familiar with, like the connection between connectivity and the second eigenvalue. Do you know of any simpler, or more direct proofs in the case of a random $r$-regular bipartite graph (rather than biregular)? I might attempt to extend such a proof to the biregular case Jan 5, 2022 at 20:43