the degree distribution of a random graph

The degree of a vertex is the number of edges meeting it, and the degree distribution is how degrees are spread across the graph. It is the first and most basic descriptor of a network's local structure, and the single statistic on which real-world networks most loudly disagree with the Erdos-Renyi model. The question it answers is: in a random graph, how many neighbours does a typical vertex have, and how much do degrees vary?

In G(n,p) the degree of a fixed vertex is a sum of n-1 independent indicators, so it is exactly Binomial(n-1, p). In the sparse regime p = lambda/n with lambda fixed, this binomial converges (law of small numbers) to a Poisson(lambda) distribution: the fraction of vertices of degree k tends to e^(-lambda) lambda^k / k!. The empirical degree distribution — the histogram of degrees over all n vertices — concentrates around this Poisson law whp (degrees of distinct vertices are only weakly dependent, and a second-moment/concentration argument controls the histogram). The key qualitative feature of the Poisson is that it is light-tailed: the chance of degree k decays super-exponentially (faster than any power), so there are essentially no high-degree 'hub' vertices, and the maximum degree in a sparse G(n,p) is only about (log n)/(log log n). The mean degree is (n-1)p, the variance is (n-1)p(1-p), and in the sparse limit both equal lambda — mean equals variance, the Poisson fingerprint.

The degree distribution matters because it is the input that local-structure theory (the branching heuristic, configuration models, Benjamini-Schramm limits) is built on, and because it is precisely where Erdos-Renyi parts ways with reality. Most observed networks — the web, citation graphs, protein interactions, social networks — have heavy-tailed, often power-law degree distributions P(degree = k) proportional to k^(-gamma), with a small number of enormously high-degree hubs that a Poisson would essentially never produce. This single empirical failure is the reason the configuration model (which lets you prescribe ANY degree sequence), Chung-Lu, and preferential attachment were invented. The honest caveat: a power-law tail and a Poisson tail are radically different objects — a Poisson has all moments finite and a sharply concentrated maximum, whereas a power law with gamma <= 3 has infinite variance, so the two models behave completely differently for robustness, epidemics, and spectral properties.