Independent Edge Sampling in G(n,p)

Building a Random Graph from Independent Choices

A graph can model a network whose links are uncertain: each possible link may or may not appear. The model \(G(n,p)\) makes this uncertainty precise by treating every possible edge as an independent Bernoulli choice with probability \(p\). The independence assumption is the central feature: it lets us calculate the probability of a specified graph by multiplying the probabilities of its individual edge and nonedge decisions.

Fix an integer \(n\ge 0\), and label the vertices \(1,\dots,n\). We use simple undirected graphs, so there are no loops or multiple edges. The set of all possible edges is \(\binom{[n]}{2}=\{\{i,j\}:1\le i<j\le n\}\), where \([n]=\{1,\dots,n\}\). Its size is \(N=\binom n2\).

Definition: The random graph \(G(n,p)\), for \(0\le p\le1\), is formed by considering each of the \(N\) possible edges separately and including it with probability \(p\), independently of all the other edge choices. A particular outcome is a labeled graph on vertex set \([n]\).

For each possible edge \(e\), its choice has two outcomes: present, with probability \(p\), or absent, with probability \(1-p\). Independence means that the probability of any complete list of these \(N\) outcomes is the product of the probabilities of the individual choices. Thus one can compute the probability of a particular graph by listing which edges it has and which possible edges it does not have.

The Probability of a Specified Graph

Theorem: Let \(H=([n],F)\) be a specified labeled simple graph, with \(F\subseteq\binom{[n]}2\). In \(G(n,p)\), the probability that the resulting graph is exactly \(H\) is \[ \Pr(G(n,p)=H)=p^{|F|}(1-p)^{N-|F|}. \] For \(p=0\) or \(p=1\), interpret this as the product of the individual edge-choice probabilities; equivalently, use \(0^0=1\).

Proof. To obtain exactly \(H\), every edge in \(F\) must be present and every edge in \(\binom{[n]}2\setminus F\) must be absent. There are \(|F|\) required present choices, each with probability \(p\), and \(N-|F|\) required absent choices, each with probability \(1-p\). These choices are independent by the definition of \(G(n,p)\), so their joint probability is \(p^{|F|}(1-p)^{N-|F|}\). The same product interpretation applies at \(p=0\) and \(p=1\), including when one of the two counts is zero. \(\square\)

This formula is for one particular labeled graph. It does not, by itself, give the probability of obtaining a graph merely isomorphic to \(H\): other choices of labeled edges may give isomorphic outcomes, and their probabilities must be added.

Proposition: If we prescribe the status—present or absent—of each edge in a set \(S\subseteq\binom{[n]}2\), then the probability of satisfying all those prescriptions is the product of the individual probabilities. In particular, if only the presence of every edge in \(F\) is required, with all other pairs unrestricted, that probability is \(p^{|F|}\).

Proof. For each prescribed edge, the required event is either “present,” of probability \(p\), or “absent,” of probability \(1-p\). The prescribed edges are distinct, so their choices are independent. Multiplying their probabilities gives the probability of all prescriptions. If only the presence of the \(|F|\) edges in \(F\) is required, no status is imposed on any other pair; those unrestricted choices contribute total probability \(1\), since their possible outcomes have probabilities \(p\) and \(1-p\), which sum to \(1\). The claimed probability is therefore \(p^{|F|}\). \(\square\)

The distinction is useful. “The graph is exactly \(H\)” specifies every possible pair. “The graph contains all edges in \(F\)” specifies only those edges; additional edges are allowed. If instead we prescribe the graph induced on a selected vertex set, we require the correct status of every pair within that set, but leave pairs with at least one endpoint outside it unrestricted.

Worked Probability Calculations

Worked Example: An Exact Path on Four Vertices

Let \(H\) have vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34\}\). Find the probability that \(G(4,1/3)\) is exactly \(H\).

There are \(\binom42=4\cdot3/2=6\) possible edges. The three present edges are \(12,23,34\); the three absent edges are \(13,14,24\). Thus the exact outcome requires three present choices, each of probability \(1/3\), and three absent choices, each of probability \(1-1/3=2/3\). Independence gives \((1/3)^3(2/3)^3=(1/27)(8/27)=8/729\).

Check: Substituting \(|F|=3\) and \(N-|F|=6-3=3\) into the exact-graph formula gives \((1/3)^3(2/3)^3=8/729\), as above. The edge list and the three nonedges together account for all six possible pairs.

Worked Example: A Prescribed Triangle That Need Not Be Induced

In \(G(5,1/3)\), find the probability that vertices \(1,2,3\) span all three triangle edges. Additional edges, including edges from these vertices to \(4\) or \(5\), are allowed. The required edge set is \(\{12,23,13\}\).

Each of these three edges must be present, so the probability is \((1/3)(1/3)(1/3)=1/27\). There are \(\binom52=5\cdot4/2=10\) possible edges in all, so seven pairs have no prescribed status. They do not change the probability: for each such pair, absence and presence together have probability \((2/3)+(1/3)=1\). For all seven unrestricted pairs, the total factor is \(1^7=1\).

Check: The required triangle edges have probability product \(1/27\), and summing over every pattern of the seven unrestricted pairs multiplies this by \((2/3+1/3)^7=1^7=1\). Hence the probability remains \(1/27\); no condition was imposed on those seven pairs.

Worked Example: The Induced Graph on Three Vertices

Let the vertex set be \(\{1,2,3,4\}\), and consider the requirement that the subgraph induced by \(\{1,2,3\}\) is exactly the path with edge set \(\{12,23\}\). Find its probability in \(G(4,1/2)\).

Within \(\{1,2,3\}\), the three possible pairs are \(12,13,23\). The requirement is that \(12\) and \(23\) be present and \(13\) be absent. Its probability is \((1/2)(1/2)(1/2)=1/8\). The other three possible edges of the four-vertex graph are \(14,24,34\). Their statuses are unrestricted, and each contributes total probability \((1/2)+(1/2)=1\). Therefore the required induced-subgraph probability is \(1/8\cdot1^3=1/8\).

Check: There are \(2^3=8\) possible status patterns on \(12,13,23\), all equally likely at \(p=1/2\), and just one pattern is the required path. The three unrestricted pairs can have any of \(2^3=8\) patterns, so \(8\) of the \(8\cdot8=64\) equally likely full graphs qualify. The ratio is \(8/64=1/8\).

Worked Example: Any Labeled Triangle with an Isolated Vertex

Find the probability that \(G(4,1/2)\) consists of a triangle and one isolated vertex, where the isolated vertex is not specified in advance. The possible edge sets are the four choices of a three-vertex subset to carry the triangle: on \(\{1,2,3\}\), \(\{1,2,4\}\), \(\{1,3,4\}\), or \(\{2,3,4\}\).

For each choice, three edges must be present and the other three pairs must be absent. For example, the triangle on \(\{1,2,3\}\) has edge set \(\{12,13,23\}\), and requires \(14,24,34\) absent. Its probability is \((1/2)^3(1/2)^3=1/64\). The same count holds for each of the other three choices. These four exact outcomes are disjoint, so their probabilities add: \(4\cdot(1/64)=4/64=1/16\).

Check: Choosing which vertex is isolated gives \(4\) choices, and each choice fixes a distinct exact graph with probability \(1/64\). Thus the total is \(4/64=1/16\). This addition is valid because a graph cannot have two different isolated vertices while its other three vertices form a triangle.

Boundary Cases and a Common Mistake

If \(n=0\) or \(n=1\), there are no possible edges, so the only graph on the prescribed vertex set is the empty-edge graph and it occurs with probability \(1\). More generally, when \(p=0\), every possible edge is absent; when \(p=1\), every possible edge is present. These deterministic cases follow directly from the edge choices, and the product formula gives the same result when factors with exponent zero are interpreted as \(1\).

Common mistake: counting only required edges when asking for an exact graph. For the path in the first example, one might calculate \((1/3)^3=1/27\) and call this the probability of obtaining exactly that path. That is only the probability that its three edges are present. It allows any of the other three pairs to be present as well. To require the exact path, the three nonedges must also be absent, so the correct calculation is \((1/3)^3(2/3)^3=8/729\). By contrast, for the triangle in the second example, the other pairs really are unrestricted, so the probability is just the product for the three required edges.

The model is useful because it makes a random graph’s construction explicit and gives a direct calculation for any fully specified labeled outcome. In every calculation, first decide what the event says about each pair: exact-graph events prescribe every pair, while containment events may leave many pairs unrestricted. Then multiply the probabilities of the prescribed choices, and add only when the event consists of several disjoint outcomes.

Check Your Understanding

For each question, identify which edge statuses are prescribed before calculating.

In \(G(4,1/2)\), what is the probability of the exact graph on \(\{1,2,3,4\}\) with edge set \(\{12,34\}\)?
In \(G(5,1/4)\), what is the probability that all edges in \(\{12,23\}\) are present, with every other pair unrestricted?
In \(G(4,1/3)\), what is the probability that the subgraph induced by \(\{1,2,3\}\) has edge set \(\{12\}\)?
Why must the probabilities of the four exact outcomes in the triangle-and-isolated-vertex example be added rather than multiplied?
What graph occurs with probability \(1\) in \(G(3,0)\), and what graph occurs with probability \(1\) in \(G(3,1)\)?