Expected Copies of a Fixed Graph

Counting Copies in a Random Graph

In the random graph $G(n,p)$, each possible edge among $n$ vertices is included independently with probability $p$. A fixed graph $F$ can appear in many different ways: its vertices can be assigned to different host vertices, and those assignments may describe the same copy. The expected number of copies depends on the number of vertices and edges of $F$, together with its symmetries.

Throughout, graphs are finite and simple. Copies mean non-induced copies: the edges of $F$ must be present on the chosen vertices, but extra host edges among those vertices are allowed. Write $v=|V(F)|$ and $e=|E(F)|$. The random graph $G(n,p)$ has vertex set $\{1,\dots,n\}$, where $n$ is a nonnegative integer and $0\le p\le1$; its possible edges are chosen independently.

Definition: An embedding of $F$ in a graph $G$ is an injective map $f:V(F)\to V(G)$ such that $f(u)f(w)\in E(G)$ whenever $uw\in E(F)$. The copy specified by $f$ consists of the vertex set $f(V(F))$ and the edge set $\{f(u)f(w):uw\in E(F)\}$. Two embeddings describe the same copy if these vertex sets and edge sets agree.

This definition permits extra edges among the image vertices. For example, a path on three vertices is a copy in a triangle: its two path edges are present, and the third edge is simply not part of the specified path. In an induced copy, by contrast, all pairs that are nonadjacent in $F$ must also be nonadjacent in the host graph.

The Expected-Copy Formula

An automorphism of $F$ is a bijection from $V(F)$ to itself that preserves adjacency in both directions. Write $\operatorname{Aut}(F)$ for the set of automorphisms and $|\operatorname{Aut}(F)|$ for its size. Also define the falling factorial $(n)_v=n(n-1)\cdots(n-v+1)$ when $n\ge v$, and set $(n)_v=0$ when $n<v$. For $v=0$, the empty product is $1$.

Theorem: Let $F$ be a fixed finite simple graph with $v$ vertices and $e$ edges. In $G(n,p)$, the expected number of non-induced copies of $F$ is $$ \mathbb{E}[X_F]=\frac{(n)_v}{|\operatorname{Aut}(F)|}\,p^e. $$ Here an edge-free $F$ has $p^0=1$, including when $p=0$.

Proof. First suppose $n\ge v$. There are $(n)_v$ injective maps $f:V(F)\to\{1,\dots,n\}$: the image of one fixed vertex has $n$ choices, the next has $n-1$ choices, and so on. These are embeddings only when all $e$ edges specified by $F$ occur in $G(n,p)$. For each fixed map, the corresponding $e$ host edges are distinct, so independence gives probability $p^e$.

Each copy is represented by exactly $|\operatorname{Aut}(F)|$ of these maps. Indeed, if two embeddings describe the same copy, composing one with the inverse of the other on the image vertices gives an adjacency-preserving bijection of $F$, hence an automorphism. Conversely, composing an embedding with any automorphism changes the vertex assignment but leaves the specified copy unchanged. Thus the number of distinct potential copies is $(n)_v/|\operatorname{Aut}(F)|$. For each potential copy, let its indicator be $1$ if all its required edges occur and $0$ otherwise. Its expected value is $p^e$. Summing these indicators counts $X_F$, and linearity of expectation gives the formula; no independence between different copies is needed. If $n<v$, there are no injective maps and both the count and the formula are zero. If $v=0$, there is one empty copy, the automorphism group has size $1$, and the formula gives $1$. $\square$

The denominator corrects for symmetry; it is not an additional probability. A highly symmetric graph has more vertex assignments that describe each one of its copies. If instead we counted embeddings, without identifying assignments that give the same copy, the expected count would be $(n)_v p^e$.

Cliques and Cycles

For a clique $K_k$, there are $k$ vertices, $\binom{k}{2}$ edges and $k!$ automorphisms, since every permutation of the vertices preserves adjacency. Consequently, for $n\ge k$,

\mathbb{E}[X_{K_k}] =\frac{(n)_k}{k!}p^{\binom{k}{2}} =\binom{n}{k}p^{\binom{k}{2}}.

The last equality uses $(n)_k/k!=\binom{n}{k}$: first choose the $k$ host vertices, then require all $\binom{k}{2}$ possible edges among them.

For a cycle $C_k$, where $k\ge3$, there are $k$ vertices and $k$ edges. Its automorphisms are the $k$ choices for the image of one fixed vertex and the two choices for the image of one of its neighbors. Once those two images are chosen, the rest of the cycle order is forced. Therefore $|\operatorname{Aut}(C_k)|=2k$, and

\mathbb{E}[X_{C_k}] =\frac{(n)_k}{2k}p^k.

Unlike the clique formula, this counts the different cycle edge sets on the chosen vertices, not just the vertex sets. Extra edges among those vertices do not invalidate a cycle copy.

Worked Example: Expected Number of Four-Cliques

Let $F=K_4$, and consider $G(6,\tfrac12)$. The graph $K_4$ has $v=4$, $e=\binom{4}{2}=6$, and $|\operatorname{Aut}(K_4)|=4!=24$. There are $(6)_4=6\cdot5\cdot4\cdot3=360$ injective assignments, so the number of distinct potential copies is $360/24=15$. Each requires six edges, with probability $(\tfrac12)^6=\tfrac1{64}$. Hence

\mathbb{E}[X_{K_4}] =15\cdot\frac1{64} =\frac{15}{64}.

Check: choosing four host vertices gives $\binom64=15$ choices. Each chosen set is a $K_4$ exactly when all six of its edges occur, an event of probability $1/64$. This independent count gives the same expectation.

Worked Example: Paths on Three Vertices

Let $F=P_3$, with vertices $a,b,c$ and edges $ab,bc$, and consider $G(5,\tfrac12)$. The path has $v=3$, $e=2$, and two automorphisms: the identity and the reversal exchanging $a$ and $c$. The number of distinct potential copies is $(5)_3/2=(5\cdot4\cdot3)/2=30$. Each copy requires two edges, so its probability is $(\tfrac12)^2=\tfrac14$. Therefore

\mathbb{E}[X_{P_3}] =30\cdot\frac14 =\frac{15}{2}.

Check: choose three host vertices in $\binom53=10$ ways. On each triple there are three choices for the middle vertex, and therefore three possible two-edge paths. Each specified path occurs with probability $1/4$. Thus the expected count is $10\cdot3\cdot\frac14=\frac{15}{2}$, as before. The value need not be an integer: it is an average over the random graphs.

Worked Example: Four-Cycles

Let $F=C_4$, and consider $G(7,\tfrac13)$. Here $v=e=4$ and $|\operatorname{Aut}(C_4)|=2\cdot4=8$. There are $(7)_4=7\cdot6\cdot5\cdot4=840$ injective assignments and $840/8=105$ distinct potential cycle copies. Each requires four specified edges, so its probability is $(\tfrac13)^4=\tfrac1{81}$. Hence

\mathbb{E}[X_{C_4}] =105\cdot\frac1{81} =\frac{35}{27}.

Check: choose four host vertices in $\binom74=35$ ways. On any four vertices there are three distinct cycles using all four vertices: fix one vertex as a start, arrange the other three in $3!=6$ orders, and identify each order with its reversal, giving $6/2=3$. Each specified cycle occurs with probability $1/81$, so the independent count is $35\cdot3\cdot\frac1{81}=\frac{105}{81}=\frac{35}{27}$.

What the Formula Does—and Does Not—Count

The factor $p^e$ records only the edges required by $F$. This is why the formula applies to non-induced copies. If induced copies are being counted instead, every one of the $\binom v2-e$ pairs that is a nonedge of $F$ must be absent. Independence then changes the probability for a fixed vertex assignment to $p^e(1-p)^{\binom v2-e}$, so the expected number of induced copies is

\frac{(n)_v}{|\operatorname{Aut}(F)|} p^e(1-p)^{\binom v2-e}.

This distinction matters even for a small graph. A triangle contains three different paths on three vertices as non-induced subgraphs, whereas it contains no induced path on three vertices.

The formula also accommodates disconnected graphs and isolated vertices. An isolated vertex contributes to $v$ and to the injective assignments, but not to $e$ or to the required-edge probability. If $F$ has no edges, every injection specifies a copy, and the formula reduces to $(n)_v/|\operatorname{Aut}(F)|$. If $p=0$ and $e>0$, the expectation is $0$; if $p=1$, every potential copy is present. These cases follow from the same count without requiring separate assumptions about connectedness.

A Common Counting Error

A frequent mistake is to count one copy per chosen vertex set and multiply by $p^e$, even when several distinct copies of $F$ can use that same set. For $P_3$ in $G(5,\tfrac12)$, this mistaken calculation gives $\binom53(\tfrac12)^2=10\cdot\frac14=\frac52$. It misses the three possible choices of middle vertex on each three-vertex set. The corrected calculation is $\binom53\cdot3\cdot\frac14=\frac{15}{2}$, in agreement with the automorphism formula. The error is not that the three path events are independent—they need not be—but that linearity of expectation counts each specified path separately.

For an induced-copy question, simply using the non-induced formula is a different error: it ignores the required absences. Before applying either formula, identify exactly what constitutes one copy and which host edges must be present or absent.

Check Your Understanding

In each question, count non-induced copies unless the question explicitly says otherwise.

Find the expected number of $K_3$ copies in $G(5,\tfrac12)$, showing the number of potential copies and the probability for each.
A fixed graph $F$ has four vertices, three edges and six automorphisms. Write the expected-copy formula in $G(n,p)$, and explain what happens when $n=3$.
Why does counting injective embeddings of $F$ require division by $|\operatorname{Aut}(F)|$ to count copies?
For $C_5$, find the number of automorphisms and write the expected number of copies in $G(n,p)$.
How does the expected count of induced copies differ from the expected count of non-induced copies?