What an Expectation Below One Actually Gives
First-moment and alteration arguments are powerful because they turn an average into an existence statement. They are also easy to overstate. An expectation below one does not mean every outcome has fewer than one obstruction, and dependent events cannot generally be treated as independent. In an alteration argument, counting cycles and counting the vertices removed to destroy them are related, but they are not the same calculation. Finally, deleting vertices has predictable effects on independence and coloring, but those effects have directions and bounds that must be stated carefully.
Throughout, graphs are finite and simple. A random graph here means a probability distribution on graphs with a specified vertex set. For a nonnegative integer-valued random variable \(X\), think of \(X\) as the number of obstructions in the outcome. For a graph \(G\) and a set \(S\subseteq V(G)\), \(G-S\) denotes the induced subgraph on \(V(G)\setminus S\). An independent set is a set of pairwise nonadjacent vertices; \(\alpha(G)\) is its maximum possible size. A proper coloring assigns colors to vertices so adjacent vertices receive different colors; \(\chi(G)\) is the minimum number of colors in such a coloring. We use \(\alpha(\varnothing)=\chi(\varnothing)=0\).
Proof. For the first claim, suppose no outcome has \(X=0\). Since \(X\) is integer-valued and nonnegative, every outcome then has \(X\ge1\), so averaging gives \(\mathbb{E}X\ge1\), contrary to the assumption. For the general claim, if every outcome had \(X\ge b\), averaging would give \(\mathbb{E}X\ge b\). Thus some outcome has \(X<b\). The strict inequality matters: \(\mathbb{E}X\le b\) alone does not imply that some outcome has \(X<b\). \(\square\)
The first statement is especially useful when \(X\) counts forbidden structures: if its expectation is strictly less than one, at least one outcome contains none. For a larger budget \(b\), the second statement gives an outcome with fewer than \(b\) obstructions. It does not say that every outcome meets the budget, or that the probability of an obstruction equals its expected count.
Worked Example: An Expected Triangle Count Below One
Choose a random graph on \(V=\{1,2,3\}\) by including each of the three possible edges \(12,23,13\) independently with probability \(1/2\). Thus each possible edge set \(E\subseteq\{12,23,13\}\) has probability \(1/8\). Let \(X\) be the number of triangles.
A triangle occurs exactly when \(E=\{12,23,13\}\). In that outcome \(X=1\); in the other seven outcomes \(X=0\). Therefore
By the first-moment existence principle, an outcome has no triangle. For an explicit check, choose \(E=\{12,23\}\). Its graph has no edge \(13\), so it has no triangle. The probability of this particular outcome is \(1/8\), and its triangle count is indeed zero.
Check: there are \(2^3=8\) equally likely edge sets; exactly one gives a triangle, so the independent direct count gives \(\mathbb{E}X=1/8\), as above. This calculation guarantees existence, not that the expected value itself is an integer count in an individual graph.
Dependence: What You May Still Add
Expectation is additive even when the events being counted are dependent. If \(X=\sum_{i=1}^r I_i\), where \(I_i\) is 1 when event \(A_i\) occurs and 0 otherwise, then
This identity follows by adding the values of the indicators outcome by outcome and then averaging. It does not require independence. By contrast, the formula \(\mathbb{P}(A\cap B)=\mathbb{P}(A)\mathbb{P}(B)\) requires \(A\) and \(B\) to be independent. The union bound, \(\mathbb{P}(\bigcup_i A_i)\le\sum_i\mathbb{P}(A_i)\), also does not require independence.
Worked Example: Two Identical Events Are Dependent
Let the sample space be \(\Omega=\{1,2,3,4\}\), with each outcome having probability \(1/4\), and let \(A=B=\{1,2\}\). Then \(\mathbb{P}(A)=\mathbb{P}(B)=2/4=1/2\), while \(A\cap B=\{1,2\}\), so \(\mathbb{P}(A\cap B)=2/4=1/2\).
A mistaken independence calculation would give \(\mathbb{P}(A\cap B)=(1/2)(1/2)=1/4\). That is wrong: the actual intersection probability is \(1/2\), so \(A\) and \(B\) are dependent. The correct union probability is \(\mathbb{P}(A\cup B)=2/4=1/2\), since \(A\cup B=\{1,2\}\). The union bound gives \(1/2\le1/2+1/2=1\), which is valid but not sharp.
Check: the indicator sum has expectation \(\mathbb{E}(I_A+I_B)=1/2+1/2=1\), without any independence assumption. In fact, \(I_A+I_B\) equals 2 on outcomes 1 and 2 and 0 on outcomes 3 and 4, so its average is \((2+2+0+0)/4=1\).
In random graphs, the events that different cycles appear are often dependent because the cycles may share edges. One may still sum their indicator expectations to find the expected number of cycles. One may not multiply the probabilities of cycle events unless independence has been established. When a proof only needs an upper bound on the probability that at least one obstruction occurs, the union bound remains available.
Cycle Counts and the Cost of Deletion
Suppose a graph contains cycles that must be removed, for example all cycles shorter than a chosen length. There are two common ways to bound deletion cost. One can choose one vertex from each cycle and delete the union of the chosen vertices; this uses at most one vertex per listed cycle. Alternatively, one can delete every vertex lying on a listed cycle; the cost is at most the sum of the cycle lengths. The second bound is often much larger. In either approach, deleting vertices cannot create a new cycle, because every edge and cycle in \(G-S\) was already present in \(G\).
Proof. For each cycle \(C\in\mathcal{C}\), choose one vertex \(v_C\) on that cycle, and let \(S=\{v_C:C\in\mathcal{C}\}\). There is at most one chosen vertex for each member of \(\mathcal{C}\), so \(|S|\le|\mathcal{C}|\), with strict inequality possible when cycles share chosen vertices. Every cycle in \(\mathcal{C}\) contains its chosen vertex and is therefore not a subgraph of \(G-S\). If \(\mathcal{C}\) contains all cycles below the threshold, every such cycle is removed. Deleting vertices cannot create another cycle, since \(G-S\) has only vertices and edges from \(G\). \(\square\)
For a random graph, apply this construction separately to each outcome. If \(X\) is the number of cycles in the collection, it gives a deletion set with \(|S|\le X\) in that outcome. Consequently, \(\mathbb{E}|S|\le\mathbb{E}X\) for this choice of deletion sets. If \(\mathbb{E}X<b\), the first-moment principle also guarantees an outcome with \(X<b\), and hence with a deletion set of size less than \(b\). This is a budget conclusion; it does not say that the deletion set has size exactly \(X\).
Worked Example: Two Triangles Sharing a Vertex
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,13,14,15,45\}\). Its cycles are exactly \(1,2,3,1\) and \(1,4,5,1\): the two triangles share vertex 1, and there are no edges joining \(\{2,3\}\) to \(\{4,5\}\).
There are \(X=2\) cycles. Choosing vertex 1 from each cycle gives \(S=\{1\}\), so \(|S|=1\le2=X\). The remaining graph has vertex set \(\{2,3,4,5\}\) and edge set \(\{23,45\}\). It contains no cycle, so both original triangles have been destroyed.
A different valid choice is to choose vertex 2 from the first triangle and vertex 4 from the second. Then \(S=\{2,4\}\) has size 2, also at most \(X\). The remaining edges are \(13\) and \(15\), and there is again no cycle. Counting the sum of the two cycle lengths gives \(3+3=6\), a valid but much weaker upper bound on the deletion cost than the one-vertex-per-cycle bound.
Check: the original graph has six edges and the two listed triangles. The first deletion removes edges \(12,13,14,15\), leaving exactly \(23,45\); these two disjoint edges cannot form a cycle.
What Vertex Deletion Can Do to \(\alpha\) and \(\chi\)
Deletion arguments often need to preserve a large independent set or a large chromatic number. The relevant bounds work in opposite directions: deleting vertices cannot increase the independence number of the remaining induced subgraph, and it cannot increase its chromatic number. But the original parameters can fall by at most the number of deleted vertices.
Proof. Any independent set in \(G-S\) is also independent in \(G\), so \(\alpha(G-S)\le\alpha(G)\). Take a maximum independent set \(I\) in \(G\). Removing its vertices in \(S\) leaves an independent set \(I\setminus S\) in \(G-S\), and \(|I\setminus S|\ge |I|-|S|=\alpha(G)-|S|\). This proves the two independence bounds, including when \(I\setminus S\) is empty.
Restricting a proper coloring of \(G\) to \(G-S\) gives a proper coloring there, so \(\chi(G-S)\le\chi(G)\). Conversely, take a proper coloring of \(G-S\) using \(\chi(G-S)\) colors. Give each vertex of \(S\) its own new color, using colors not assigned to \(G-S\). This colors all of \(G\) properly and uses at most \(\chi(G-S)+|S|\) colors. Hence \(\chi(G)\le\chi(G-S)+|S|\), which is equivalent to \(\chi(G)-|S|\le\chi(G-S)\). If \(G-S\) is empty, the stated convention \(\chi(\varnothing)=0\) makes the same construction valid. \(\square\)
For a single deleted vertex \(v\), these inequalities show that \(\alpha(G-v)\) is either \(\alpha(G)\) or \(\alpha(G)-1\), and \(\chi(G-v)\) is either \(\chi(G)\) or \(\chi(G)-1\). The statement is about the amount of change, not a guarantee that either parameter changes. For a larger set \(S\), the loss in either parameter is at most \(|S|\).
Worked Example: Deleting a Vertex from a Disjoint Edge and Isolate
Let \(G\) have \(V=\{1,2,3\}\) and \(E=\{12\}\), and delete \(S=\{3\}\). In \(G\), an independent set can contain vertex 3 and one of 1 or 2, so \(\alpha(G)=2\). It cannot contain all three vertices because 1 and 2 are adjacent. In \(G-S\), the graph has vertices \(\{1,2\}\) and edge set \(\{12\}\), so \(\alpha(G-S)=1\). Thus the independence number drops by exactly one, matching \(\alpha(G)-|S|=2-1=1\).
The original graph has \(\chi(G)=2\): vertices 1 and 2 need different colors, and vertex 3 may reuse either color. The remaining edge requires two colors, so \(\chi(G-S)=2\). Here deleting the vertex does not lower the chromatic number. The bounds give \(2-1=1\le2\le2\) for \(\chi(G-S)\), as required.
Check: the remaining graph has one edge, so its independence number is 1 and its chromatic number is 2. Both direct calculations satisfy the deletion inequalities.
Common Errors to Check Before Concluding
“The expectation is below one, so every outcome has no obstruction.” The conclusion is only that some outcome has none. Other outcomes may have one or more. If the expectation equals one rather than being strictly below one, the zero-obstruction conclusion does not follow from this argument.
“The obstruction events are dependent, so their expected count cannot be added.” This reverses the relevant rule. Linearity of expectation always permits adding the individual event probabilities for the expected count. Dependence matters when multiplying probabilities, not when adding expectations.
“There are \(X\) cycles, so deleting cycles costs exactly \(X\) vertices.” The one-vertex-per-cycle construction gives an upper bound of \(X\), not an equality. Cycles can share a chosen vertex, as in the worked example. A sum of cycle lengths is another upper bound when deleting all their vertices, but it is generally not the number of distinct vertices deleted.
“Deleting vertices can raise the independence number, or the original chromatic number is at most the remaining one.” For induced vertex deletion, every remaining independent set was already independent in the original graph, and a coloring of the original graph restricts to the remaining graph. Thus \(\alpha(G-S)\le\alpha(G)\) and \(\chi(G-S)\le\chi(G)\). The reverse comparisons require the additive \(|S|\) allowance proved above.
Check Your Understanding
For each question, distinguish what follows from a bound from what would require an additional assumption.
- If \(X\) is a nonnegative integer-valued random variable with \(\mathbb{E}X=0.9\), what does the first-moment existence principle guarantee? Does it say every outcome has \(X=0\)?
- Give a reason why \(\mathbb{E}(I_A+I_B)=\mathbb{P}(A)+\mathbb{P}(B)\) holds even when \(A\) and \(B\) are dependent.
- If a graph has \(r\) cycles in a specified collection, what upper bound does choosing one vertex per cycle give on the size of a deletion set that destroys them all?
- For a set \(S\) of \(k\) deleted vertices, state the lower bounds on \(\alpha(G-S)\) and \(\chi(G-S)\) in terms of the original parameters.
- Why does \(\mathbb{E}X\le b\), without strict inequality, not by itself guarantee an outcome with \(X<b\)?