Random Construction Followed by Deletion
A random graph need not satisfy a desired restriction: it may contain many copies of a forbidden graph. The alteration method does not require the random graph to be suitable as it stands. Instead, it first constructs a random graph and then deletes vertices to destroy all forbidden copies. If the number of copies is small compared with the number of vertices, the resulting graph can still be large.
All graphs in this tutorial are finite and simple. For an integer \(n\ge 0\), the random graph \(G(n,p)\), where \(0\le p\le1\), has vertex set \(\{1,\dots,n\}\); each possible edge is included independently with probability \(p\). An induced subgraph on a vertex set \(W\) retains exactly the edges of the original graph whose two endpoints both lie in \(W\). In particular, deleting vertices produces an induced subgraph.
The basic idea is to find a small set that hits every forbidden copy. A direct way to do this is to list the copies and choose one vertex from each. This may choose the same vertex more than once, so the number of distinct vertices deleted is at most the number of copies. Overlap can make the deletion much cheaper.
The Basic Alteration Principle
Proof. Fix any outcome \(G\) of the random construction. For each \(F\)-copy in \(G\), select one of its vertices, and let \(S\) be the set of all selected vertices. If \(X\) is the number of copies, then \(|S|\le X\), because selecting the same vertex for multiple copies increases the number of selections but not the size of their union. Delete \(S\). Any \(F\)-copy in the remaining induced subgraph would also have been an \(F\)-copy in \(G\), and the selected vertex for that original copy would belong to \(S\). That vertex was deleted, contradicting the existence of the copy in the remaining graph. Thus the remaining graph is \(F\)-free and has \(n-|S|\ge n-X\) vertices.
Now apply this procedure to every outcome of the random construction, and let \(Y\) be the number of vertices left. For every outcome, \(Y\ge n-X\), so \(\mathbb{E}Y\ge n-\mathbb{E}X\). Some outcome has \(Y\ge n-\mathbb{E}X\); otherwise every value of \(Y\) would be smaller than that lower bound, forcing its expectation to be smaller as well. Since \(Y\) is integer-valued, \(Y\ge\lceil n-\mathbb{E}X\rceil\). \(\square\)
For \(F=K_r\), the complete graph on \(r\) vertices, a \(K_r\)-copy appears exactly when all \(\binom r2\) edges within its \(r\)-vertex set are present. Therefore, in \(G(n,p)\),
Indeed, each of the \(\binom nr\) vertex sets contributes an indicator that equals \(1\) precisely when all its \(\binom r2\) edges are present. The probability of that event is \(p^{\binom r2}\), and adding the indicators gives the displayed expectation. The alteration theorem then gives an \(K_r\)-free induced subgraph of order at least \(\left\lceil n-\binom{n}{r}p^{\binom r2}\right\rceil\). The bound is useful when the expected number of forbidden copies is substantially smaller than \(n\).
Worked Example: Altering a Six-Vertex Random Graph
Consider \(G(6,1/2)\), and take \(F=K_3\), so the forbidden copies are triangles. There are \(\binom 63=20\) possible vertex triples. Each triple is a triangle with probability \((1/2)^3=1/8\), because all three of its edges must be present. Hence
The alteration principle guarantees an outcome leaving at least \(6-\frac52=\frac72\) vertices. The number left must be an integer, so some outcome leaves at least \(\lceil 7/2\rceil=4\) vertices in a triangle-free induced subgraph.
Check: the computation uses \(20\) possible triples and probability \(1/8\) for each, giving \(5/2\) expected triangles. Since \(6-5/2=7/2\), an integer number of remaining vertices must be at least \(4\) in some outcome. The conclusion is an existence guarantee; it does not claim that every outcome leaves four vertices.
Following the Deletion Step
The proof gives a concrete procedure after a graph has been constructed: inspect its forbidden copies, select a vertex from each, and delete the union of the selected vertices. Here is a small deterministic trace that illustrates why counting copies bounds the number of vertices lost.
Worked Example: Two Triangles Sharing a Vertex
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,13,34,45,35\}\). Its triangles are \(123\) and \(345\), and they share vertex \(3\). Process the copies in the listed order and select vertex \(3\) from each:
| Stage | Copy processed | Selected vertices so far | Vertices remaining |
|---|---|---|---|
| Start | None | \(\varnothing\) | \(\{1,2,3,4,5\}\) |
| 1 | \(123\) | \(\{3\}\) | \(\{1,2,4,5\}\) |
| 2 | \(345\) | \(\{3\}\) | \(\{1,2,4,5\}\) |
The final induced subgraph has edges \(12\) and \(45\), so it contains no triangle. There were two triangles, but only one distinct vertex was deleted. The general guarantee is that at most two vertices are deleted here; the actual deletion set has size one.
Check: deleting vertex \(3\) removes edges \(23,13,34,35\), leaving precisely \(12\) and \(45\). These two disjoint edges contain no triangle, and the remaining vertex count is \(5-1=4\).
Controlling Edges as Well as Vertices
Sometimes the aim is not merely to retain many vertices, but to keep many edges too. Deleting a vertex can remove all of its incident edges. In a simple graph on \(n\) vertices, every vertex has degree at most \(n-1\). Thus deleting a set \(S\) removes at most \((n-1)|S|\) edges: every removed edge has at least one endpoint in \(S\), and counting degrees of vertices in \(S\) counts every such edge at least once.
Proof. For a fixed outcome, the deletion set \(S\) from the theorem satisfies \(|S|\le X\). Every edge lost has an endpoint in \(S\). The sum of the degrees in the original graph over vertices in \(S\) counts each lost edge at least once, and each such degree is at most \(n-1\). Therefore the number of lost edges is at most \((n-1)|S|\le(n-1)X\), so at least \(M-(n-1)X\) edges remain. Taking expectations shows that the expected number of remaining edges is at least \(\mathbb{E}M-(n-1)\mathbb{E}X\). Some outcome attains at least this lower bound, since otherwise the expectation would be smaller. The resulting graph is \(F\)-free by the deletion theorem, and its edge count is an integer. \(\square\)
Worked Example: A Triangle-Free Graph with Several Edges
Use \(G(6,1/4)\) and delete vertices to destroy all triangles. The expected number of edges is \(\binom 62(1/4)=15/4\), since there are \(15\) possible edges and each is present with probability \(1/4\). There are \(20\) possible triples, and the probability that a triple forms a triangle is \((1/4)^3=1/64\). Thus the expected number of triangles is \(20/64=5/16\).
Each deleted vertex has degree at most \(5\), so the proposition gives the following lower bound on the expected number of remaining edges:
Since \(35/16=2+3/16\), some outcome, after alteration, has at least \(\lceil 35/16\rceil=3\) edges and no triangle.
Check: the edge expectation is \(15(1/4)=15/4\); the triangle expectation is \(20(1/64)=5/16\); and the maximum-degree factor is \(6-1=5\). Substitution gives \(15/4-25/16=35/16\), so rounding up yields three edges. As an independent consistency check, the graph on \(\{1,2,3,4,5,6\}\) with edges \(12,23,34,41\) has four edges, no triangle, and two isolated vertices. It confirms that a six-vertex triangle-free graph with at least three edges is possible, although it need not be the particular outcome supplied by the random argument.
Choosing Parameters and Avoiding a Common Error
The probability \(p\) controls a trade-off. Increasing \(p\) raises the expected number of edges, but also raises the expected number of copies that must be destroyed. The alteration estimate makes this tension explicit: for forbidden cliques, the expected deletion cost in vertices is \(\binom nr p^{\binom r2}\), while the expected initial edge count is \(\binom n2p\). One chooses parameters so that the obstruction cost is small enough for the desired conclusion. A bound that is negative or too small may still be correct, but it does not establish a useful large graph.
Common mistake: treating copies as distinct deleted vertices. In the two-triangle example, there are two triangles, but deleting their common vertex \(3\) destroys both. The incorrect calculation “two triangles means exactly two vertices are lost” confuses the number of copies with the size of a set hitting them. The valid statement is \(|S|\le X\), not \(|S|=X\). Consequently, \(n-\mathbb{E}X\) is a lower bound on the number of vertices retained by the alteration, not an equality in general.
The method is useful because it separates a construction into two manageable tasks: estimate how often a random object violates the restriction, then show that removing the violations costs little. It does not require the random graph itself to be free of forbidden subgraphs. The guarantee comes from bounding the total deletion cost and converting an average bound into at least one successful outcome.
Check Your Understanding
Use the deletion principle and show the intermediate estimates in each answer.
- In \(G(5,1/2)\), compute the expected number of triangles and the resulting guaranteed lower bound on the order of a triangle-free induced subgraph.
- Explain why selecting one vertex from every \(F\)-copy produces a set of size at most the number of copies, even when some copies overlap.
- For a graph on \(n\) vertices, justify why deleting \(s\) vertices removes at most \((n-1)s\) edges.
- In \(G(6,1/3)\), compute the expected number of edges and triangles, then apply the edge-loss estimate to decide whether it guarantees a positive number of remaining edges.
- Give an example of two forbidden copies that share a vertex, and explain why their number need not equal the number of vertices needed to hit them both.