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 '17 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 '17 at 20:40

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, privacy policy and cookie policy

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