Average degree of graph and degree

Let $G$ be a graph on $n$ vertices on which we impose that the average degree is a constant $d$. Is it true that as $n \to \infty$ the degree of each node will be a Poisson-distributed random variable? I heard this claim in passing, saw no proof and I might misremember a crucial detail, so if any graph theorist knows of any claim that sounds similar, I would be very grateful.

Solution 1:

Suppose $G$ is chosen by taking $n$ vertices $v_1, \dots, v_n$ and adding each possible edge $v_i v_j$ independently with probability $\frac{d}{n-1}$. Then for each $v_i$, $\deg(v_i)$ has the $\text{Binomial}(n, \frac{d}{n-1})$ distribution.

This distribution has expected value $d$ (so we get the average degree we wanted), and converges to $\text{Poisson}(d)$ as $n \to \infty$.

The content of this statement is that $$ \lim_{n \to \infty} \binom nk \left(\frac d{n-1}\right)^k \left(1 - \frac{d}{n-1}\right)^{n-1-k} = e^{-d} \frac{d^k}{k!} $$ for each constant $k$. This is true because:

• $\binom nk \sim \frac{n^k}{k!}$ as $n \to \infty$.
• $\left(\frac d{n-1}\right)^k \sim \frac{d^k}{n^k}$ as $n \to \infty$, which cancels with the previous factor to get $\frac{d^k}{k!}$.
• $\left(1 - \frac{d}{n-1}\right)^{n-1-k} \sim \left(1 - \frac d{n-1}\right)^{n-1}$ as $n\to \infty$.
• $\lim_{n \to \infty} \left(1 - \frac d{n-1}\right)^{n-1} = \lim_{n \to \infty} \left(1 - \frac d n\right)^n$ is exactly the limit definition of $e^{-d}$.