# the joint distribution of the degrees of an Erdős–Rényi graph

Does the joint distribution of the degrees of an Erdős–Rényi graph have a closed form?

• I don't think it's going to have a closed form as its highly dependent on the graph structure: You'd have to incorporate some kind of inclusion-exclusion summing over vertices and edges. Aug 25, 2016 at 16:25

Let $D=(d_1, d_2, \dots, d_n)$ be any viable degree distribution on $n$ labelled vertices with $\sum_{i=1}^{i=n}d_i=2m$. Let $\mathcal{H}_D$ be the set of all graphs which have degree distribution $D$.
Now suppose $\mathbf{G}$ is an Erdős–Rényi random graph on $n$ vertices with edge probability $p$. If $H \in \mathcal{H}_D$, then $$\mathbb{P}(\mathbf{G}=H)=p^m(1-p)^{{n\choose{2}}-m}$$ since all graphs in $\mathcal{H}_D$ have $m$ edges. Therefore, $$\mathbb{P}(\mathbf{G} \in \mathcal{H}_D)= \sum_{H \in \mathcal{H}_D} \mathbb{P}(\mathbf{G}=H)$$ $$\mathbb{P}(\mathbf{G} \in \mathcal{H}_D) = |\mathcal{H}_D|\times p^m(1-p)^{{n\choose{2}}-m}$$ As far as I know, there is no closed form for $|\mathcal{H}_D|$ -- although there might be one if we allow for self-edges (in which case the $n\choose 2$ will be replaced by $n^2$).
• @ToneyShields huh? In the labelled case, each $d_i$ (the number of edges of vertex $i$) is binomial. So, the joint distribution of $(d_1,d_2,\ldots,d_n)$ (which this answer is considering) is indeed a joint distribution of dependent Binomial random variables -- even the one you were asking about. Sep 4, 2016 at 5:55
• Do you understand how to get, say, the joint distribution of degrees of an ER graph with $3$ vertices and $p=0.3$ by just manually considering all possible graphs? Sep 4, 2016 at 11:45
• @ToneyShields Correct (so it seems I was wrong and the issue is not with the definition of joint distribution). But that probability is what this answer is considering - the probability that the vector of degrees is some $D=(d_1,\ldots,d_n)$. And in the $3$-vertex case, I don't know which part you have trouble with -- to find, say, $f(d_1=2,d_2=1,d_3=1)$ just go over all (if any) graphs that produce those degrees and sum the probabilities. Sep 5, 2016 at 14:37