Expected Edge Counts and Degree Distributions

From Independent Edges to Expected Counts

In the random graph model $G(n,p)$, every possible edge is included independently with probability $p$. This makes the number of edges and the degree of a specified vertex binomial random variables. The expected number of vertices of a given degree then follows by summing indicator variables; the degrees of different vertices need not be independent for this expectation calculation.

Definition: For an integer $n\ge 1$ and $p\in[0,1]$, $G(n,p)$ is a random simple graph with vertex set $V=\{1,\ldots,n\}$. Each of the $\binom{n}{2}$ possible edges is included with probability $p$, independently of every other possible edge. A particular graph $H$ on this vertex set with $j$ edges therefore occurs with probability $p^j(1-p)^{\binom{n}{2}-j}$ when $0<p<1$. For $p=0$ or $p=1$, the model is respectively the empty graph or the complete graph.

Let $X$ denote the random number of edges, and, for a vertex $v$, let $D_v=\deg(v)$ denote its random degree. For $k\in\{0,\ldots,n-1\}$, let $N_k$ denote the random number of vertices of degree exactly $k$. In particular, $N_0$ is the number of isolated vertices. Expectations are averages over the random graph outcomes.

Distributions of the Edge Count and a Degree

Theorem: In $G(n,p)$, $X$ has a binomial distribution with $\binom{n}{2}$ trials and success probability $p$. For each fixed vertex $v$, $D_v$ has a binomial distribution with $n-1$ trials and success probability $p$. Thus, for $0<p<1$, $$ \Pr(X=j)=\binom{\binom{n}{2}}{j}p^j(1-p)^{\binom{n}{2}-j},\qquad \Pr(D_v=k)=\binom{n-1}{k}p^k(1-p)^{n-1-k}. $$ The endpoint cases $p=0,1$ are the corresponding degenerate distributions.

Proof. For each possible edge $e$, define $I_e=1$ if $e$ is included and $I_e=0$ otherwise. Each $I_e$ equals $1$ with probability $p$, and these variables are independent by the definition of $G(n,p)$. The edge count is $X=\sum_e I_e$, where the sum has $\binom{n}{2}$ terms. The event $X=j$ occurs exactly when some set of $j$ possible edges is included and all other possible edges are absent. There are $\binom{\binom{n}{2}}{j}$ choices for that set, and each choice has probability $p^j(1-p)^{\binom{n}{2}-j}$. These mutually exclusive possibilities give the stated formula.

For a fixed vertex $v$, precisely $n-1$ possible edges meet $v$. Its degree is the sum of the $n-1$ inclusion indicators for those edges. The same counting argument, now choosing $k$ included edges from those $n-1$, gives the stated degree formula. If $p=0$, every indicator is $0$; if $p=1$, every indicator is $1$. These give the asserted endpoint distributions. $\square$

A binomial random variable with $r$ trials and success probability $p$ has expectation $rp$: write it as a sum of $r$ indicators, each with expectation $p$, and use linearity of expectation. Consequently,

\mathbb{E}[X]=\binom{n}{2}p,\qquad \mathbb{E}[D_v]=(n-1)p.

Linearity of expectation applies whether or not the variables being added are independent. This distinction matters for vertex degrees: $D_u$ and $D_v$ share the indicator for edge $uv$, so they are generally dependent. But the expected number of vertices of a given degree can still be computed by adding the individual probabilities.

Expected Numbers of Vertices by Degree

Proposition: For $0\le k\le n-1$, the expected number $N_k$ of vertices of degree exactly $k$ in $G(n,p)$ is $$ \mathbb{E}[N_k] =n\binom{n-1}{k}p^k(1-p)^{n-1-k}, $$ with endpoint cases interpreted using the degenerate distributions. In particular, $$ \mathbb{E}[N_0]=n(1-p)^{n-1}. $$

Proof. For each vertex $v$, define $J_v=1$ if $\deg(v)=k$, and $J_v=0$ otherwise. Then $N_k=\sum_{v\in V}J_v$, because each vertex of degree $k$ contributes one and every other vertex contributes zero. By the degree distribution, $\mathbb{E}[J_v]=\Pr(D_v=k)=\binom{n-1}{k}p^k(1-p)^{n-1-k}$ for $0<p<1$. There are $n$ vertices, and each has this same probability. Linearity of expectation gives the formula for $\mathbb{E}[N_k]$, without any assumption that the $J_v$ are independent. For $k=0$, the formula becomes $n(1-p)^{n-1}$. At $p=0$, all $n$ vertices have degree zero; at $p=1$, only the case $n=1$ has an isolated vertex, as also specified by the degenerate degree distribution. $\square$

The expected values $\mathbb{E}[N_k]$ are not themselves probabilities: they can be fractional, and some may exceed $1$. They describe average counts across many outcomes. As a consistency check, every graph on $n$ vertices has exactly $n$ vertices in total, so summing the degree-count expectations over $k$ must give $n$. The binomial theorem confirms this:

\sum_{k=0}^{n-1}\mathbb{E}[N_k] =n\sum_{k=0}^{n-1}\binom{n-1}{k}p^k(1-p)^{n-1-k} =n\bigl(p+(1-p)\bigr)^{n-1} =n.

There is another useful check. In every graph, the sum of all vertex degrees is twice the number of edges, since each edge contributes one to the degree at each endpoint. Taking expectations gives $\sum_{k=0}^{n-1}k\,\mathbb{E}[N_k]=2\binom{n}{2}p$. The degree-count formula agrees: its left side is $n(n-1)p$, equal to $2\binom{n}{2}p$.

Worked Example: The Edge-Count Distribution

Take $G(4,\frac13)$, with vertex set $V=\{1,2,3,4\}$ and possible edge set $\{12,13,14,23,24,34\}$. Write $X$ for the number of included edges. There are $\binom{4}{2}=6$ possible edges, so $X$ has a binomial distribution with six trials and success probability $1/3$.

For each $j$, the probability is $\binom{6}{j}(1/3)^j(2/3)^{6-j}$. The common denominator is $3^6=729$. Substitution gives the following probabilities, listed in order for $j=0,1,\ldots,6$:

\Pr(X=j)=\frac{1}{729}(64,192,240,160,60,12,1).

For instance, the numerator for $j=2$ is $\binom62 2^4=15\cdot16=240$. To check the full distribution, its numerators sum to $64+192+240+160+60+12+1=729$, so the probabilities sum to $1$. Its expected edge count from the binomial mean is $6\cdot\frac13=2$.

Check: Weighting the listed probabilities by their edge counts gives $(0\cdot64+1\cdot192+2\cdot240+3\cdot160+4\cdot60+5\cdot12+6\cdot1)/729=1458/729=2$, in agreement with the mean formula.

Worked Example: Expected Counts for Every Degree

Take $G(5,\frac12)$, with vertex set $V=\{1,2,3,4,5\}$ and possible edge set $\{ij:1\le i<j\le5\}$. A fixed vertex has four possible incident edges, so its degree has probabilities $(1,4,6,4,1)/16$ for degrees $0,1,2,3,4$, respectively. Multiplying each probability by the five vertices gives

\bigl(\mathbb{E}[N_0],\mathbb{E}[N_1],\mathbb{E}[N_2],\mathbb{E}[N_3],\mathbb{E}[N_4]\bigr) =\left(\frac5{16},\frac54,\frac{15}{8},\frac54,\frac5{16}\right).

For example, $\mathbb{E}[N_2]=5\binom42(1/2)^2(1/2)^2=5\cdot6/16=30/16=15/8$. These are averages, not a prediction that one realized graph must have a fractional number of vertices of any degree.

Check: The expected counts sum to $(5+20+30+20+5)/16=80/16=5$, the number of vertices. Their degree-weighted sum is $(1\cdot20+2\cdot30+3\cdot20+4\cdot5)/16=160/16=10$. Independently, there are $\binom52=10$ possible edges, so the expected edge count is $10\cdot\frac12=5$, and twice this is $10$, as required.

Worked Example: Isolated Vertices in $G(6,\frac13)$

Let $V=\{1,2,3,4,5,6\}$, with possible edge set $\{ij:1\le i<j\le6\}$. A specified vertex is isolated exactly when all five possible edges incident to it are absent. Independence gives probability $(2/3)^5=32/243$. Therefore, if $N_0$ is the number of isolated vertices,

\mathbb{E}[N_0]=6\left(\frac23\right)^5 =\frac{6\cdot32}{243} =\frac{192}{243} =\frac{64}{81}.

The expected number of vertices of degree exactly $2$ is also available from the same degree distribution:

\mathbb{E}[N_2] =6\binom52\left(\frac13\right)^2\left(\frac23\right)^3 =\frac{6\cdot10\cdot1\cdot8}{3^5} =\frac{480}{243} =\frac{160}{81}.

Check: The probabilities for degrees $0$ through $5$ at one vertex have numerators $32,80,80,40,10,1$ over $243$. They sum to $243/243=1$. Multiplying by six gives expected counts summing to $6$. The expected edge count is $\binom62/3=15/3=5$, so the expected sum of degrees is $2\cdot5=10$. From the degree-count numerators it is $(1\cdot480+2\cdot480+3\cdot240+4\cdot60+5\cdot6)/243=2430/243=10$.

A Common Counting Pitfall

When testing whether a vertex is isolated, count only the possible edges incident to that vertex. In $G(5,\frac12)$, a specified vertex has four possible incident edges. Its isolation probability is therefore $(1/2)^4=1/16$, and the expected number of isolated vertices is $5/16$. A common incorrect calculation uses all $\binom52=10$ possible edges and obtains $(1/2)^{10}$ for the isolation probability, hence $5/1024$ for the expected count. That event is instead the probability that the entire graph is empty; it is much more restrictive than requiring one vertex to be isolated.

The method is broadly reusable: identify the local event for one vertex, calculate its probability using the incident edge trials, then sum its indicator over the vertices. Independence between different vertices is not needed for this expectation calculation. Questions about how much the realized count fluctuates around its expectation require additional arguments.

Check Your Understanding

Use the binomial distributions and indicator-variable method to answer the following.

In $G(7,\frac14)$, what is the distribution and expected value of the number of edges?
In $G(6,\frac12)$, what is the probability that a specified vertex has degree exactly $3$?
For general $n$ and $p$, derive the expected number of vertices of degree $1$.
In $G(4,\frac13)$, calculate the expected number of isolated vertices. How many possible edges incident to a fixed vertex determine its isolation?
Explain why the expected number of vertices of degree $k$ can be found by summing probabilities even though the degrees of different vertices are generally dependent.

Expected Edge Counts and Degree Distributions

What You'll Learn

From Independent Edges to Expected Counts

Distributions of the Edge Count and a Degree

Expected Numbers of Vertices by Degree

Worked Example: The Edge-Count Distribution

Worked Example: Expected Counts for Every Degree

Worked Example: Isolated Vertices in \(G(6,\frac13)\)

A Common Counting Pitfall

Check Your Understanding

Expected Edge Counts and Degree Distributions

What You'll Learn

From Independent Edges to Expected Counts

Distributions of the Edge Count and a Degree

Expected Numbers of Vertices by Degree

Worked Example: The Edge-Count Distribution

Worked Example: Expected Counts for Every Degree

Worked Example: Isolated Vertices in \(G(6,\frac13)\)

A Common Counting Pitfall

Check Your Understanding

Previous

Next