<p>For constant <span class="math-container">$d \geq 3$</span>, a random <span class="math-container">$d$</span>-regular graph is connected with high probability. In fact, it is an expander with high probability. See for example <a href="https://snap.stanford.edu/class/cs224w-readings/ellis11expansion.pdf" rel="nofollow noreferrer">this note</a> by David Ellis. Friedman even showed that a random <span class="math-container">$d$</span>-regular graph has nearly optimal spectral gap, with high probability.</p>

CC BY-SA 4.0
2024-01-08T12:02:59.997Z
The link you offered  is not found now.
Jxb
CC BY-SA 4.0
2024-01-08T12:12:13.400Z
how to prove the existence of $d$-regular expander graph with probabilistic method?
Jxb
CC BY-SA 4.0
2024-01-12T12:55:43.370Z
See my answer here: https://mathoverflow.net/a/132509/34591
Hermann Gruber
CC BY-SA 4.0
2024-01-14T18:11:11.967Z
@Jxb I noticed that the link in the MO answer was broken. Sorry about that - I just have fixed it.
Hermann Gruber
CC BY-SA 4.0
2017-03-02T03:05:28.040Z
2024-01-09T17:58:19.937Z
2024-01-09T17:58:19.937Z
Yuval Filmus
<p>An Erdős–Rényi graph over <span class="math-container">$n$</span> vertices and average degree <span class="math-container">$d$</span> is not connected w.h.p. iff <span class="math-container">$d &lt; \log n$</span>. I was wondering for what the degree <span class="math-container">$d$</span> would a random regular graph of degree <span class="math-container">$d$</span> be connected? In particular will this be connected for some degree less than <span class="math-container">$\log n$</span>?</p>

CC BY-SA 3.0
2017-03-02T15:15:59.493Z
BTW, Vivek, you should accept answers if they do answer the question as posed.
Sasho Nikolov
CC BY-SA 3.0
2017-03-02T20:40:13.550Z
I will to read/glance the paper and then accept the answer. Thanks for letting me know though!
Vivek Bagaria
<reference-request><graph-theory><randomness><random-graphs>
Connectivity of a random regular graph of degree $d$
Vivek Bagaria
# Connectivity of a random regular graph of degree $d$

(Asked by: username_0 on 2017-03-02)

An Erdős–Rényi graph over $n$ vertices and average degree $d$ is not connected w.h.p. 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$?

**Tags:** reference-request, graph-theory, randomness, random-graphs
> **Comments:**
> **username_1**: BTW, Vivek, you should accept answers if they do answer the question as posed.  
> **username_0**: I will to read/glance the paper and then accept the answer. Thanks for letting me know though!  

---

## 1 answers

### Answer by username_2 on 2017-03-02. Score: 15 | Accepted answer

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](https://snap.stanford.edu/class/cs224w-readings/ellis11expansion.pdf) by David Ellis. Friedman even showed that a random $d$-regular graph has nearly optimal spectral gap, with high probability.

> **Comments:**
> **username_3**: The link you offered  is not found now.  
> **username_3**: how to prove the existence of $d$-regular expander graph with probabilistic method?  
> **username_4**: See my answer here: https://mathoverflow.net/a/132509/34591  
> **username_4**: @Jxb I noticed that the link in the MO answer was broken. Sorry about that - I just have fixed it.  

---

