# 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.

• Is that where you saw it? jsums.edu/nmeghanathan/files/2015/08/… Commented Dec 9, 2021 at 20:24
• No, I literally heard someone say it, but that is indeed the claim. Do you know where I can find an actual proof? @markvs
– Karl
Commented Dec 9, 2021 at 20:29
• I do not know but if I needed it, I would send a message to Dr. Natarajan Meghanathan. Commented Dec 9, 2021 at 20:31
• So to clarify, $G$ is not just a graph with average degree $d$, but rather a random graph uniformly picked among such graphs? Commented Dec 9, 2021 at 20:36
• I guess you are right @HagenvonEitzen, it is a sparse network with average degree $d<<$ number of nodes
– Karl
Commented Dec 9, 2021 at 20:45

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}$$.