Uniform Fixed-Edge Sampling in G(n,m)

The Fixed-Edge Model

In independent edge sampling, each possible edge is chosen separately with the same probability. A different model fixes the total number of edges in advance, then chooses which edges they are. This distinction changes joint probabilities: in the fixed-edge model, selecting one edge leaves fewer available edges for the remaining choices.

All graphs here are finite, simple and undirected. For an integer $n\ge 1$, let $K_n$ be the complete graph on $n$ vertices, so every pair of distinct vertices is an edge. Write $N=\binom{n}{2}$ for its number of possible edges. The parameter $m$ is an integer with $0\le m\le N$.

Definition: The random graph $G(n,m)$ is chosen uniformly from all graphs on a fixed set of $n$ vertices with exactly $m$ edges. Equivalently, choose an $m$-element subset of the $N$ edges of $K_n$, with every such subset having probability $1/\binom{N}{m}$.

Thus the sample space contains $\binom{N}{m}$ possible graphs, not $2^N$ equally likely graphs: only graphs with exactly $m$ edges are in the sample space. When $m=0$, the only outcome is the graph with no edges. When $m=N$, the only outcome is $K_n$. If $n=1$, then $N=0$, so $m=0$ and there is again just one outcome.

Probabilities for Prescribed Edges

To ask whether a specified subgraph occurs, first specify its required edges. Let $F$ be a set of $k$ distinct edges of $K_n$. The event that all edges in $F$ are present is obtained by including those $k$ edges and choosing the remaining $m-k$ edges from the other $N-k$ possibilities.

Theorem: In $G(n,m)$, for a fixed set $F$ of $k$ possible edges, $$ \Pr(F\subseteq E(G))= \frac{\binom{N-k}{m-k}}{\binom{N}{m}} $$ when $k\le m$. If $k>m$, the probability is $0$. In the feasible case $k\le m$, the same probability can be written $$ \Pr(F\subseteq E(G))= \frac{m(m-1)\cdots(m-k+1)}{N(N-1)\cdots(N-k+1)}, $$ with the probability of the empty edge set $F=\varnothing$ equal to $1$.

Proof. There are $\binom{N}{m}$ equally likely outcomes. If $k>m$, no outcome with only $m$ edges can contain all $k$ required edges, so the probability is $0$. If $k\le m$, every favorable outcome includes all $k$ edges of $F$. Its remaining $m-k$ edges must be selected from the $N-k$ edges not in $F$, giving $\binom{N-k}{m-k}$ favorable outcomes. Dividing by the total number of outcomes proves the binomial-coefficient formula. For $k\ge1$, cancellation of factorials gives $\binom{N-k}{m-k}/\binom{N}{m}=m!(N-k)!/((m-k)!N!)$, which is the displayed product. For $k=0$, there is no restriction, so the probability is $1$. $\square$

The product form also has a sequential interpretation: reveal the membership of the $k$ specified edges one at a time. Given that the first $i$ specified edges are present, $m-i$ of the remaining $N-i$ edges are selected, so the next specified edge has conditional probability $(m-i)/(N-i)$, whenever the preceding event has positive probability. Multiplying these factors gives the product above.

Worked Example: A Specified Triangle

Let the vertex set be $V=\{1,2,3,4,5\}$, and let the possible edges be $E(K_5)=\{12,13,14,15,23,24,25,34,35,45\}$. Choose a graph uniformly from those with $m=4$ edges. Find the probability that the three edges of the triangle on $\{1,2,3\}$ are all present.

Here $N=\binom{5}{2}=10$, and the required edge set is $F=\{12,13,23\}$, so $k=3$. The total number of possible outcomes is $\binom{10}{4}=10\cdot9\cdot8\cdot7/(4\cdot3\cdot2\cdot1)=210$. If the three required edges are included, one more edge must be chosen from the seven other edges. There are $\binom{7}{1}=7$ such choices. Therefore $\Pr(F\subseteq E(G))=7/210=1/30$.

Check: The product formula gives $(4/10)(3/9)(2/8)=24/720=1/30$, agreeing with the count. The event does not require the other two vertices to be isolated; the one remaining edge may be any of the seven edges not in $F$.

Prescribing Both Edges and Nonedges

Sometimes the question specifies an exact pattern on a fixed set of vertices. For this, require both the edges of the pattern and the absence of its other possible edges. Let $F$ be the set of required edges and $A$ the set of required nonedges, viewed as possible edges of the complete host graph that must be absent. Assume $F\cap A=\varnothing$. If $k=|F|$ and $\ell=|A|$, then the other $N-k-\ell$ edges are unrestricted.

Counting rule: For disjoint sets $F,A$ of required present and absent edges, respectively, $$ \Pr\big(F\subseteq E(G),\ A\cap E(G)=\varnothing\big) = \frac{\binom{N-k-\ell}{m-k}}{\binom{N}{m}}. $$ A binomial coefficient is taken to be $0$ if its lower argument is less than $0$ or greater than its upper argument. This convention makes the formula $0$ whenever the requirements are impossible.

Indeed, a favorable graph must include all $k$ edges of $F$, none of the $\ell$ edges of $A$, and exactly $m-k$ further edges from the $N-k-\ell$ unrestricted edges. Counting those choices and dividing by $\binom{N}{m}$ gives the rule. This argument also proves the stated zero probability when the requested edge count cannot be achieved.

Worked Example: An Induced Path on Three Fixed Vertices

Use the same vertex set $V=\{1,2,3,4,5\}$, the same ten possible edges of $K_5$, and choose exactly $m=4$ edges. Find the probability that the subgraph induced by $\{1,2,3\}$ has exactly the edges $12$ and $23$, so that $13$ is absent.

Here $F=\{12,23\}$, so $k=2$, and $A=\{13\}$, so $\ell=1$. The seven unrestricted edges are $\{14,15,24,25,34,35,45\}$. Both required edges are present, leaving $4-2=2$ edges to select from those seven. There are $\binom{7}{2}=7\cdot6/(2\cdot1)=21$ favorable outcomes, while the total number of outcomes is $\binom{10}{4}=210$. The probability is $21/210=1/10$.

Check: Every favorable outcome consists of $12$, $23$, and two of the seven unrestricted edges, and therefore has exactly four edges. The required nonedge $13$ is excluded from those choices, so the induced subgraph on the specified three vertices is exactly the path $1,2,3$.

Why Edges Are Dependent

In $G(n,m)$, the edge count is fixed, so edge-presence events are generally dependent. The next result quantifies this for any two distinct possible edges. For a possible edge $e$, let $X_e$ be $1$ if $e$ is selected and $0$ otherwise.

Proposition: Suppose $N\ge2$, and let $e,f$ be distinct possible edges. In $G(n,m)$, $$ \Pr(e\in E(G))=\frac{m}{N},\qquad \Pr(e,f\in E(G))=\frac{m(m-1)}{N(N-1)}. $$ If $0<m<N$, then $$ \operatorname{Cov}(X_e,X_f) =-\frac{m(N-m)}{N^2(N-1)}<0. $$ For $m=0$ or $m=N$, both indicators are constant, so their covariance is $0$.

Proof. For $m\ge1$, the probability that $e$ is selected is $\binom{N-1}{m-1}/\binom{N}{m}=m/N$; for $m=0$, it is $0=m/N$. For $m\ge2$, the probability that both $e$ and $f$ are selected is $\binom{N-2}{m-2}/\binom{N}{m}=m(m-1)/(N(N-1))$; for $m=0$ or $m=1$, it is $0$, also given by that expression. Since $\mathbb{E}[X_eX_f]=\Pr(e,f\in E(G))$ and $\mathbb{E}[X_e]=\mathbb{E}[X_f]=m/N$, their covariance is \[ \frac{m(m-1)}{N(N-1)}-\frac{m^2}{N^2} = \frac{mN(m-1)-m^2(N-1)}{N^2(N-1)} = -\frac{m(N-m)}{N^2(N-1)}. \] This is strictly negative when $0<m<N$. At either endpoint $m=0$ or $m=N$, every possible edge is respectively absent or present in every outcome, so the indicators are constant and have covariance $0$. $\square$

Equivalently, when $0<m<N$, after learning that $e$ is present, the probability that $f$ is present is $(m-1)/(N-1)$. This is less than the marginal probability $m/N$, since $(m-1)/(N-1)<m/N$ is equivalent to $N(m-1)<m(N-1)$, or $N>m$. Fixing one edge as present leaves one fewer selected edge among the remaining possibilities.

Fixed-Edge Sampling Versus Independent Sampling

In $G(n,p)$, each of the $N$ possible edges is included independently with probability $p$. Thus, for $k$ distinct specified edges, the probability that all are present is $p^k$; if $\ell$ other specified edges must be absent, the probability is $p^k(1-p)^\ell$. These formulas follow from independence. In $G(n,m)$, by contrast, the edge count is exactly $m$, and the corresponding probability is the counting formula above.

The value $p=m/N$ makes the one-edge probability agree in the two models, but it does not generally make probabilities of multiple edges agree. Matching the marginal probability of one edge does not remove the dependence created by fixing the total number of edges.

Worked Example: A Triangle Anywhere in $K_4$

Let $V=\{1,2,3,4\}$, with possible edge set $E(K_4)=\{12,13,14,23,24,34\}$. Choose exactly $m=3$ edges, and find the probability that the chosen graph contains at least one triangle.

The total number of outcomes is $\binom{6}{3}=6\cdot5\cdot4/(3\cdot2\cdot1)=20$. The four possible triangles have edge sets $\{12,13,23\}$, $\{12,14,24\}$, $\{13,14,34\}$, and $\{23,24,34\}$. Each is one favorable outcome, since choosing three edges that contain a triangle leaves no room for any additional edge. No outcome is counted for two different triangles: the union of the edge sets of any two distinct triangles in $K_4$ has five edges, but an outcome here has only three. Hence there are four favorable outcomes and the probability is $4/20=1/5$.

Check: Counting by the four distinct three-edge triangle sets gives $4$ favorable outcomes out of $20$, as above. If instead the edges were sampled independently with $p=m/N=3/6=1/2$, the probability that one particular triangle’s three edges were all present would be $(1/2)^3=1/8$. That is not the probability of a triangle anywhere, and it is not the fixed-edge probability for a specified triangle. The models answer different probability questions.

Common Pitfall

Do not replace a fixed edge count by independent trials with $p=m/N$. In the first example, $N=10$, $m=4$, and the three specified edges have fixed-edge probability $1/30$. The incorrect independent-sampling calculation would use $p=4/10=2/5$ and give $p^3=(2/5)^3=8/125$, which is not $1/30$. The correct calculation counts the $7$ ways to choose the one remaining edge among $210$ equally likely four-edge graphs, giving $7/210=1/30$. The shortcut fails because $G(n,m)$ fixes the total number of edges; its edge events are not independent.

When using these rules, identify whether the question specifies only required edges or an exact induced pattern. For a non-induced occurrence on fixed vertices, count with the required edges and leave all other edges unrestricted. For an induced pattern, also mark the required nonedges and exclude them from the available choices. Finally, check feasibility: more required edges than $m$, or a total specification incompatible with $m$, gives probability zero.

Check Your Understanding

Use the fixed-edge counting rule and state whether each specification is feasible.

In $G(6,5)$, what is the probability that two specified distinct edges are both present?
In $G(5,2)$, what is the probability that three specified distinct edges are all present?
In $G(5,4)$, find the probability that one specified edge is present and two other specified edges are absent.
Explain why the probability that two distinct edges are both present in $G(n,m)$ need not equal $(m/N)^2$.
For an exact induced pattern on a fixed vertex set, which two types of edge requirements must be counted?

Uniform Fixed-Edge Sampling in G(n,m)

What You'll Learn

The Fixed-Edge Model

Probabilities for Prescribed Edges

Worked Example: A Specified Triangle

Prescribing Both Edges and Nonedges

Worked Example: An Induced Path on Three Fixed Vertices

Why Edges Are Dependent

Fixed-Edge Sampling Versus Independent Sampling

Worked Example: A Triangle Anywhere in \(K_4\)

Common Pitfall

Check Your Understanding

Uniform Fixed-Edge Sampling in G(n,m)

What You'll Learn

The Fixed-Edge Model

Probabilities for Prescribed Edges

Worked Example: A Specified Triangle

Prescribing Both Edges and Nonedges

Worked Example: An Induced Path on Three Fixed Vertices

Why Edges Are Dependent

Fixed-Edge Sampling Versus Independent Sampling

Worked Example: A Triangle Anywhere in \(K_4\)

Common Pitfall

Check Your Understanding

Previous

Next