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

  • $\begingroup$ 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." $\endgroup$ Jan 2, 2022 at 20:57
  • $\begingroup$ 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 $\endgroup$ Jan 2, 2022 at 22:52

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

  • $\begingroup$ 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 $\endgroup$ Jan 5, 2022 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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