In a connected random graph, when the degree of each node is at least 2？

Question

In random graphs, we know while $p>ln(n)/n$, the graph is connected.

In a connected graph, I want to know when the degree of each node is at least 2 ?

If $X$ is ${B(n,p)}$ $n\to+\infty$

When $p$ meets the conditions, $P(X\ge2)\to1 $

$P(X\ge2)=1-P(X=0)-P(X=1)=1-\frac{{\lambda^0}e^{-\lambda}}{0!} + \frac{\lambda^1e^{-\lambda}}{1!}=1-(1+\lambda) e^{-\lambda}$

$\lambda $ is $np$

We need $(1+\lambda)e^{-\lambda}\to o(1)$

I guess $p>ln(2n)/n$

Answer 1

First of all, you're being very sloppy when you say "when $p > \frac{\log n}{n}$, the graph is connected". Whenever we make any nontrivial statements about a random graph, they aren't always true; they're only true with probability tending to $1$. More importantly, when $p = \frac{\log n}{n}$, the graph still has isolated vertices with probability about $\frac 1e$, and that's not going to change as soon as $p > \frac{\log n}{n}$. Actually, the condition for being connected with high probability is for $np - \log n \to \infty$ as $n \to \infty$.

---

Anyway, the probability to look at for minimum degree $2$ is $\frac{\log n + \log \log n}{n}$. More precisely, if we write the edge probability as $$ p = \frac{\log n + \log \log n + c_n}{n} $$ (equivalently, if we define $c_n = np - \log n - \log \log n$) then the limiting probability of the graph having minimum degree at least $2$ is

• $0$, if $c_n \to -\infty$ as $n \to \infty$,
• $e^{-e^{-c}}$, if $c_n \to c$ as $n \to \infty$,
• $1$, if $c_n \to \infty$ as $n \to \infty$.

The second bullet is the key fact, the other two follow from monotonicity.

The idea is that (in the range of $p$ for which $c_n \to c$) the degree of a vertex can be approximated by a Poisson random variable with mean $\lambda = np$. The Poisson distribution is $0$ or $1$ with probability $(1+\lambda) e^{-\lambda}$. Asymptotically, $$ (1+\lambda) e^{-\lambda} = \frac{\log n + \log \log n + c_n}{n \cdot \log n \cdot e^{c_n}} = (1 + o(1)) \frac1n e^{-c}. $$ So the expected number of vertices with degree $0$ or $1$ is $(1 + o(1)) e^{-c}$. The number of those vertices can, again, be approximated by a Poisson random variable as $n \to \infty$, and the probability that that Poisson random variable is $0$ is $e^{-e^{-c}}$.

I didn't prove the Poisson approximation facts, but generally this is done by the method of moments: for a random variable $X$ depending on $n$, if $\mathbb E[X(X-1)\dots(X-k+1)] \to \lambda^k$ as $n \to \infty$ for any fixed $k$, then $X$ is asymptotically Poisson-distributed with mean $\lambda$. This is the typical thing to see, in the context of random graphs, when a random variable has constant mean as $n \to \infty$.

For minimum degree $d$, replace $\log \log n$ by $(d-1)\log\log n$.