From an Average Count to an Existing Graph
Random choices can prove that a graph with a specified property exists even when no particular construction is apparent. The useful setup is to count the objects that would prevent the desired property: for example, isolated vertices or vertices whose degrees are too small. If the expected number of such objects is less than one, then at least one outcome has none. The reason is the integer nature of the count: a positive count must be at least one.
We work with finite probability spaces, such as the set of all graphs on a fixed vertex set with each graph assigned a probability. An outcome is considered possible if it has positive probability. For a random variable \(X\), its expectation is the probability-weighted average of its values. If \(A\) is an event, its indicator \(\mathbf{1}_A\) is \(1\) when \(A\) occurs and \(0\) otherwise; in particular, \(\mathbb{E}[\mathbf{1}_A]=\Pr(A)\). Linearity of expectation gives \(\mathbb{E}[\sum_i X_i]=\sum_i\mathbb{E}[X_i]\), whether or not the variables \(X_i\) are independent.
In a graph application, define \(X\) to be the number of bad vertices, edges, or other obstructions. The lemma then says there is an outcome with no such obstruction. The expectation is not required to be an integer; a fractional expectation below one is precisely what makes the conclusion useful.
Proof and a Threshold Version
Proof. For every nonnegative integer \(X\), the pointwise inequality \(\mathbf{1}_{\{X\ge 1\}}\le X\) holds: if \(X=0\), both sides are zero, and if \(X\ge1\), the right side is at least one. Taking expectations gives \(\Pr(X\ge1)\le\mathbb{E}[X]<1\). Since the events \(X\ge1\) and \(X=0\) partition the outcomes, \(\Pr(X=0)=1-\Pr(X\ge1)>0\). Thus at least one outcome of positive probability has \(X=0\). \(\square\)
Proof. Suppose no positive-probability outcome has \(X\le r\). Then \(X\ge r+1\) on every positive-probability outcome, so averaging its values gives \(\mathbb{E}[X]\ge r+1\). This contradicts the assumed strict inequality. Therefore an outcome with \(X\le r\) exists. \(\square\)
The lemma is the special case \(r=0\). The threshold form is useful when a construction can tolerate a small number of defects. In either form, the strict inequality matters: a random variable that is always \(1\) has expectation \(1\), but never takes the value \(0\).
Worked Graph-Existence Examples
Worked Example: A Graph with No Isolated Vertices
Choose a graph uniformly at random from all simple graphs on \(V=\{1,2,3,4\}\). Equivalently, include each of the six possible edges independently with probability \(1/2\). Let \(X\) be the number of isolated vertices, where an isolated vertex has degree zero.
For a fixed vertex, its three possible incident edges must all be absent for it to be isolated. There are \(2^3=8\) equally likely choices for those three edges, and exactly one choice has all three absent. Thus the probability that a fixed vertex is isolated is \(1/8\). Write \(X\) as the sum of the four indicators of isolation. By linearity of expectation,
The first-moment lemma guarantees a graph with \(X=0\), so with no isolated vertices. For an explicit check, take \(E=\{12,23,34,41\}\). Each of the four vertices is incident with two listed edges, so the graph has no isolated vertices and \(X=0\). This verifies the property directly.
Check: The expectation calculation used four vertex indicators, each with probability \(1/8\), giving \(1/2\). In the displayed graph each vertex has degree \(2\), so the counted number is indeed zero.
Worked Example: A Graph with Minimum Degree at Least Two
Choose a graph uniformly at random on \(V=\{1,2,3,4,5,6,7\}\), again including each possible edge independently with probability \(1/2\). Call a vertex bad if its degree is at most \(1\), and let \(X\) count the bad vertices. A fixed vertex has six possible incident edges. Among the \(2^6=64\) equally likely choices, one choice gives degree \(0\), and six choices give degree \(1\), according to which single edge is present. Therefore
Summing the seven vertex indicators gives
Hence some graph has \(X=0\), which means every vertex has degree at least \(2\). One explicit example is the graph with \(V=\{1,2,3,4,5,6,7\}\) and \(E=\{12,23,34,45,56,67,71\}\). Each vertex is incident with exactly two listed edges. Thus every degree is \(2\), and no vertex is bad.
Check: The displayed edge set has seven edges, one joining each consecutive pair around the cycle, including \(71\). Each of the seven vertices occurs in exactly two edges, so the minimum degree is \(2\), as the existence conclusion requires.
Worked Example: A Tournament with No Sink
A tournament is a directed graph formed by orienting each edge of a complete graph in exactly one direction. Choose each orientation independently and uniformly at random on \(V=\{1,2,3,4\}\). A sink is a vertex with no outgoing edge. Let \(X\) be the number of sinks.
A fixed vertex is a sink precisely when all three edges incident with it point towards it. Of the \(2^3=8\) possible orientations of those edges, exactly one has this property. Its probability of being a sink is therefore \(1/8\). Adding the four sink indicators yields
The lemma guarantees a tournament with no sink. For a direct verification, orient the six edges as \(1\to2\), \(2\to3\), \(3\to1\), \(4\to1\), \(2\to4\), and \(3\to4\). The outgoing edges are \(1\to2\) for vertex \(1\); \(2\to3\) and \(2\to4\) for vertex \(2\); \(3\to1\) and \(3\to4\) for vertex \(3\); and \(4\to1\) for vertex \(4\). Each vertex has at least one outgoing edge, so \(X=0\).
Check: There are \(\binom42=6\) pairs and the list assigns exactly one direction to each: \(12,23,13,14,24,34\). Each vertex has at least one listed outgoing edge, verifying that the orientation is a tournament with no sink.
What the Lemma Does—and Does Not—Say
The argument is an existence proof, not a formula for the probability that the desired outcome occurs. From \(\mathbb{E}[X]<1\), it follows that \(\Pr(X=0)>0\), but the value of that probability may require a separate calculation. Nor does the lemma say that every outcome is good: some outcomes can have many obstructions while a positive-probability set has none.
Common mistake: treating the expectation as a probability. In the first example, \(\mathbb{E}[X]=1/2\) does not imply that the probability of having no isolated vertices is \(1/2\). In fact, the number of four-vertex graphs with no isolated vertices is \(41\): with two edges there are \(3\) disjoint pairs; with three edges there are \(20-4=16\) choices, since the four triangles leave one vertex isolated; with four, five, or six edges there are respectively \(15\), \(6\), or \(1\) choices, all without an isolated vertex. Thus the probability is \(41/64\), not \(1/2\). The lemma needs only that this probability is positive.
Common mistake: dropping the strict inequality. If \(X=1\) for every outcome, then \(\mathbb{E}[X]=1\), but no outcome has \(X=0\). So an expectation equal to one does not suffice. Also, the integer-valued condition is essential to the threshold reasoning: a nonnegative real-valued variable can always be positive while having expectation below one, as a constant value of \(1/2\) shows.
To use the method reliably, identify the undesirable objects, define an integer-valued count \(X\), calculate its expectation, and check that the bound is strictly below one. Then \(X=0\) is exactly the desired property. The calculation of the expectation often uses indicator variables and linearity; independence is needed for some individual probability calculations, but not for adding the expectations.
Check Your Understanding
For each question, identify the integer-valued count and state precisely what the expectation bound would guarantee.
- Why does \(\mathbb{E}[X]<1\) imply \(\Pr(X=0)>0\) when \(X\) is nonnegative and integer-valued?
- If \(X\) counts vertices of degree zero in a random graph and \(\mathbb{E}[X]=3/4\), what graph property is guaranteed to occur in some outcome?
- For a nonnegative integer-valued \(X\), what conclusion follows from \(\mathbb{E}[X]<4\)?
- Give an example showing why the conclusion \(X=0\) need not follow when \(\mathbb{E}[X]=1\).
- In the seven-vertex example, why is the probability that a fixed vertex has degree at most \(1\) equal to \(7/64\)?