Random Graphs as a Finite Probability Space
Existence proofs sometimes ask whether a graph with a collection of desired features can be found. Instead of constructing one directly, we can choose a graph at random and calculate the probability that the desired features occur. The basic model makes each possible edge an independent choice, so requirements about a small set of edges can be computed explicitly. Here the emphasis is on setting up that model and calculating pattern probabilities; more advanced arguments can build on these calculations.
For \(0<p<1\), every possible labeled graph has positive probability. The endpoint cases are deterministic: \(G(n,0)\) has no edges, and \(G(n,1)\) has every possible edge. When \(n=0\) or \(n=1\), there are no possible edges, so the outcome is the unique graph on the specified vertex set.
Independence means that for any distinct possible edges, prescribing which ones are present and which ones are absent gives a probability equal to the product of the individual probabilities. The graph is simple, so possible edges are unordered pairs of distinct vertices; loops and multiple edges are not part of this model.
Probability of a Prescribed Edge Pattern
Proof. Suppose first that \(0<p<1\). For each edge in \(F\), the required outcome has probability \(p\), and for each edge in \(B\), it has probability \(1-p\). The choices for all distinct possible edges are independent by the definition of \(G(n,p)\). Therefore the probability that all the \(|F|+|B|\) requirements hold is the product of their probabilities: \(p\) appears \(|F|\) times and \(1-p\) appears \(|B|\) times, giving \(p^{|F|}(1-p)^{|B|}\). At \(p=0\) and \(p=1\), the graph is deterministic, so the event occurs exactly when its requirements match that graph. \(\square\)
Edges outside \(F\cup B\) are unrestricted. This distinction is important: requiring the edges of a graph as a subgraph does not rule out extra edges, while requiring an induced subgraph also prescribes the absent edges among the selected vertices.
Worked Example: Requiring a Path on Three Selected Vertices
Take \(G(4,p)\), with vertex set \(V=\{1,2,3,4\}\). Require edges \(12\) and \(23\) to be present and edge \(13\) to be absent. Thus \(F=\{12,23\}\) and \(B=\{13\}\); the edges \(14,24,34\) are unrestricted. On the selected vertices \(\{1,2,3\}\), the required induced subgraph is the path with edge set \(\{12,23\}\).
By the edge-pattern formula, the probability is \(p^2(1-p)\). For \(p=\frac13\), this is $$ \left(\frac13\right)^2\left(1-\frac13\right) =\frac19\cdot\frac23 =\frac{2}{27}. $$
Check: the three required choices contribute \(\frac13,\frac13,\frac23\), whose product is \(\frac{2}{27}\). The three unrestricted edges can be chosen in any way. Summing over their eight possible patterns multiplies this probability by \(\bigl(\frac13+\frac23\bigr)^3=1\), so leaving them unrestricted does not change the result.
More generally, if we require a particular set \(F\) of edges to be present and impose no conditions on any other edges, the probability is \(p^{|F|}\). To require the induced graph on a vertex set \(S\) to have edge set \(F\), we must also put every possible edge within \(S\) that is not in \(F\) into \(B\). Edges with at least one endpoint outside \(S\) remain unrestricted unless further conditions are imposed.
Worked Example: An Exact Labeled Cycle
Let \(V=\{1,2,3,4\}\). The exact labeled cycle with edge set \(E=\{12,23,34,14\}\) requires \(F=\{12,23,34,14\}\) and \(B=\{13,24\}\). In \(G(4,p)\), the probability of this exact graph is $$ p^4(1-p)^2. $$
At \(p=\frac12\), substitution gives $$ \left(\frac12\right)^4\left(\frac12\right)^2 =\frac1{16}\cdot\frac14 =\frac1{64}. $$
Check: there are \(\binom42=6\) possible edges on these four vertices. Four must be present and the other two absent, so each of the six independent choices has probability \(\frac12\); their product is \((\frac12)^6=\frac1{64}\), as above. This is the probability of this one labeled edge set, not the probability that the outcome is any cycle on four vertices.
Exact Graphs and Edge Counts
Proof. To obtain exactly \(H\), each of its \(m\) edges must be present, and each of the other \(\binom n2-m\) possible edges must be absent. These are disjoint requirements on independent edge choices. Applying the edge-pattern formula with \(F=E(H)\) and with \(B\) the set of all other possible edges gives the displayed probability. \(\square\)
For a fixed vertex set, there are \(\binom{\binom n2}{m}\) labeled graphs with exactly \(m\) edges: choose which \(m\) of the \(\binom n2\) possible edges are present. These exact outcomes are disjoint. Consequently, the probability that \(G(n,p)\) has exactly \(m\) edges is $$ \binom{\binom n2}{m}p^m(1-p)^{\binom n2-m}. $$ This counts outcomes with a specified edge total, not graphs with a specified structural property.
Worked Example: Exactly Two Edges in \(G(4,\frac13)\)
Here \(V=\{1,2,3,4\}\), so there are \(\binom42=6\) possible edges. The number of outcomes with exactly two edges is \(\binom62=15\): select two edges from the six. Every such labeled graph has probability $$ \left(\frac13\right)^2\left(1-\frac13\right)^4 =\frac19\left(\frac23\right)^4 =\frac{16}{729}. $$
Adding the probabilities of the 15 disjoint outcomes gives $$ 15\cdot\frac{16}{729}=\frac{240}{729}=\frac{80}{243}. $$
Check by the formula: substituting \(n=4\), \(m=2\), and \(p=\frac13\) into the edge-count expression gives $$ \binom{\binom42}{2}\left(\frac13\right)^2\left(\frac23\right)^4 =15\cdot\frac19\cdot\frac{16}{81} =\frac{80}{243}. $$ The independent count of 15 edge sets and the formula agree.
From Positive Probability to Existence
Proof. A finite probability space assigns nonnegative probabilities to its outcomes, and the probability of an event is the sum of the probabilities of the outcomes in that event. If the event contained no outcomes, its probability would be the empty sum, which is \(0\). Therefore an event with positive probability contains at least one outcome. \(\square\)
In graph applications, the outcomes are graphs. Thus a positive probability for a collection of required properties proves that at least one graph has those properties. The calculation need not identify which outcome works. This is the basic existence-proof mechanism: define a random graph, describe an event precisely, and show that its probability is positive. The difficult part in more substantial applications is often choosing the event and estimating its probability.
Worked Example: A Positive-Probability Exact Path
Consider the graph \(H\) on \(V=\{1,2,3,4\}\) with edge set \(E(H)=\{12,23,34\}\), a path on four vertices. In \(G(4,\frac12)\), exact equality with \(H\) requires those three edges present and the other three possible edges \(13,14,24\) absent. Therefore $$ \Pr(G(4,\tfrac12)=H) =\left(\frac12\right)^3\left(\frac12\right)^3 =\frac1{64}>0. $$
By the existence principle, at least one outcome of this random experiment is the graph \(H\) itself. This particular conclusion is also witnessed explicitly by \(H\), but the probability calculation illustrates the general logical step: positive probability rules out the possibility that every outcome fails the requirements.
Check: there are six possible edges, and an exact labeled graph on four vertices prescribes all six choices. Each choice has probability \(\frac12\), so the product is \((\frac12)^6=\frac1{64}\), matching the calculation from three present and three absent edges.
Common Pitfall: Subgraph Versus Induced Subgraph
A frequent error is to calculate only the probability of required present edges when the problem also forbids extra edges. For example, in \(G(4,\frac13)\), requiring edges \(12\) and \(23\) to be present has probability \((\frac13)^2=\frac19\), because the other edges are unrestricted. But requiring the induced graph on \(\{1,2,3\}\) to be exactly the path with edge set \(\{12,23\}\) also requires \(13\) absent. Its probability is $$ \left(\frac13\right)^2\left(1-\frac13\right) =\frac19\cdot\frac23 =\frac{2}{27}, $$ not \(\frac19\). The missing factor \(\frac23\) is the probability that \(13\) is absent.
For an exact graph on all \(n\) vertices, every possible edge must be accounted for: edges in the graph are prescribed present, and all remaining possible edges are prescribed absent. If some edges are left unspecified, the event is broader and its probability must not be described as the probability of that exact graph.
Using the Model Carefully
The parameter \(p\) controls the probability of each individual edge, not the probability of every graph property. For example, a specified set of \(a\) edges appears with probability \(p^a\) when no other edges are restricted. If \(b\) additional edges are required absent, the probability becomes \(p^a(1-p)^b\). These are direct consequences of independence, and the distinction between the two events should be made before substituting a value of \(p\).
At \(p=\frac12\), every one of the \(2^{\binom n2}\) labeled graphs has probability \(2^{-\binom n2}\), since each possible edge is independently present or absent with probability \(\frac12\). At other values of \(p\), graphs with different numbers of edges generally have different probabilities, as the exact-graph formula shows. In either case, probabilities concern the random choice of a labeled graph; they do not alter the definitions of graph properties such as being a path or a cycle.
Check Your Understanding
For each question, distinguish present-edge requirements from absent-edge requirements before calculating.
- In \(G(5,\frac12)\), what is the probability that edges \(12,23,34\) are all present, with no conditions on other edges?
- In \(G(4,p)\), find the probability that the induced graph on \(\{1,2,3\}\) has edge set \(\{12,23\}\).
- For a fixed labeled graph \(H\) on \(n\) vertices with \(m\) edges, explain why its exact-graph probability has \(m\) factors of \(p\) and \(\binom n2-m\) factors of \(1-p\).
- In \(G(4,\frac13)\), how many labeled outcomes have exactly one edge, and what is the probability of each one?
- State and justify the implication from an event having positive probability to the existence of a graph satisfying that event.