An Erdos-Renyi graph over $n$ vertices and average degree $d$ is not connected whp iff $d < \log n$. I was wondering for what the degree $d$ would a random regular graph of degree $d$ be connected? In particular will this be connected for some degree less than $\log n$?

  • $\begingroup$ BTW, Vivek, you should accept answers if they do answer the question as posed. $\endgroup$ Mar 2, 2017 at 15:15
  • $\begingroup$ I will to read/glance the paper and then accept the answer. Thanks for letting me know though! $\endgroup$ Mar 2, 2017 at 20:40

1 Answer 1


For constant $d \geq 3$, a random $d$-regular graph is connected with high probability. In fact, it is an expander with high probability. See for example this note by David Ellis. Friedman even showed that a random $d$-regular graph has nearly optimal spectral gap, with high probability.


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.