Extremal Numbers: The Basic Question
Extremal graph theory asks how many edges a graph can have while avoiding a specified pattern. The forbidden pattern is fixed, while the number of vertices of the graph being optimized can vary. This turns a qualitative condition—“contains no copy of \(H\)”—into a numerical maximum. The key convention is that a copy is an ordinary subgraph, not necessarily an induced subgraph.
The condition that \(H\) has at least one edge is part of this definition. We write \(h=|V(H)|\). If \(n<h\), no graph on \(n\) vertices can contain \(H\) as a subgraph, so every graph on \(n\) vertices is \(H\)-free. In particular, \(\operatorname{ex}(n,H)=\binom{n}{2}\) in that case. If \(n\ge h\), there are finitely many simple graphs on \(n\) vertices, so a maximum exists. An \(H\)-free graph with \(\operatorname{ex}(n,H)\) edges is called an extremal graph for \(H\) on \(n\) vertices. There can be more than one such graph.
Every graph on \(n\) vertices has at most \(\binom{n}{2}\) edges, since each edge is a distinct unordered pair of vertices. Therefore \(\operatorname{ex}(n,H)\le \binom{n}{2}\). The point of the subject is to improve this bound by using the structure of \(H\), and to find constructions that show a proposed bound is sharp.
Ordinary and Induced Avoidance
For an ordinary subgraph, we may choose some vertices and some of the edges between them. For an induced subgraph on a chosen vertex set, we must include every edge of the original graph whose two endpoints are in that set. Consequently, being \(H\)-free in the ordinary sense is a different condition from having no induced subgraph isomorphic to \(H\).
Worked Example: A Triangle Contains a Path as a Subgraph
Let \(H=P_3\), the path on three vertices with two edges. Consider the simple graph \(G\) with vertex set \(V(G)=\{1,2,3\}\) and edge set \(E(G)=\{12,23,13\}\). This is a triangle. It contains \(P_3\) as an ordinary subgraph: choose vertices \(1,2,3\) and edges \(12,23\), leaving edge \(13\) out of the chosen subgraph. Thus \(G\) is not \(P_3\)-free in the ordinary sense.
On the other hand, the induced subgraph on all three vertices has all three edges, so it is a triangle, not \(P_3\). There are no other three-vertex subsets to check. Thus \(G\) has no induced subgraph isomorphic to \(P_3\). This example shows why the definition of \(\operatorname{ex}(n,H)\) must specify ordinary, rather than induced, subgraph avoidance.
Check: the selected ordinary subgraph has exactly the two edges \(12\) and \(23\), which form a path on three vertices. The induced subgraph must also include \(13\), giving three edges instead of two.
Some useful implications follow directly from the definitions. If \(F\) is a subgraph of \(H\), any graph that avoids \(F\) automatically avoids \(H\): a copy of \(H\) would contain a copy of \(F\). The converse need not hold. For example, avoiding a single edge forces a graph to avoid a triangle, but avoiding a triangle does not force a graph to avoid a single edge.
Proof. Fix \(n\), and take any \(F\)-free graph \(G\) on \(n\) vertices. If \(G\) contained a copy of \(H\), then that copy would contain a copy of \(F\), because \(F\) is a subgraph of \(H\). This would contradict that \(G\) is \(F\)-free. Therefore every \(F\)-free graph is \(H\)-free. The set of \(F\)-free graphs on \(n\) vertices is consequently a subset of the set of \(H\)-free graphs on \(n\) vertices. Maximizing the number of edges over the smaller set cannot give a larger maximum, so \(\operatorname{ex}(n,F)\le\operatorname{ex}(n,H)\). The hypothesis that \(F\) has an edge ensures that \(\operatorname{ex}(n,F)\) is defined under our convention; since \(F\) is a subgraph of \(H\), \(H\) also has an edge. \(\square\)
Two Exact Basic Cases
Forbidding a single edge is the most restrictive case: an \(H\)-free graph with \(H=K_2\) cannot have any edges. Forbidding a path on three vertices permits edges, but no vertex can be incident with two of them. These observations give exact answers, not merely upper bounds.
Proof. A graph contains \(K_2\) as a subgraph exactly when it has an edge. Thus a \(K_2\)-free graph has zero edges, and the edgeless graph on \(n\) vertices attains zero. This includes \(n=0\).
Now consider \(P_3\). A graph contains \(P_3\) as a subgraph exactly when some vertex has two distinct neighbors: the two edges from that vertex to its neighbors form a copy of \(P_3\). Hence a \(P_3\)-free graph has maximum degree at most \(1\), and conversely any graph with maximum degree at most \(1\) is \(P_3\)-free. In such a graph the sum of the degrees is at most \(n\). By the handshake lemma, the sum of the degrees is twice the number of edges, so the number of edges is at most \(\lfloor n/2\rfloor\). To attain this bound, take \(\lfloor n/2\rfloor\) pairwise disjoint edges and, when \(n\) is odd, one isolated vertex. No vertex has degree greater than \(1\), so the graph is \(P_3\)-free and has exactly \(\lfloor n/2\rfloor\) edges. The upper bound and construction prove the formula, including \(n=0\) and \(n=1\). \(\square\)
Worked Example: The Extremal Number for \(P_3\) on Six Vertices
Let \(H=P_3\) and \(n=6\). The theorem gives \(\operatorname{ex}(6,P_3)=\lfloor 6/2\rfloor=3\). Here is an extremal graph explicitly: \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,34,56\}\). Each vertex has degree \(1\), so no vertex has two distinct neighbors and \(G\) contains no \(P_3\). It has three edges, attaining the claimed maximum.
Check: the degree sum is \(1+1+1+1+1+1=6\), so the handshake lemma gives \(|E(G)|=6/2=3\). For the upper bound, every \(P_3\)-free graph on six vertices has degree sum at most \(6\), and hence has at most \(6/2=3\) edges. The construction and upper bound agree.
An Averaging Upper Bound
A general way to obtain an upper bound is to inspect all vertex subsets of one fixed size. If every such subset induces a graph with at most a known number of edges, then counting how often each edge appears gives a bound on the total number of edges. The induced graph is used for counting, but the forbidden condition remains ordinary subgraph avoidance: every induced subgraph of an \(H\)-free graph is still \(H\)-free.
Proof. Let \(G\) be any \(H\)-free graph on \(n\) vertices, and write \(m=|E(G)|\). For each \(h\)-element subset \(S\) of \(V(G)\), the induced graph \(G[S]\) is \(H\)-free: if \(G[S]\) contained a copy of \(H\), the same vertices and edges would give a copy of \(H\) in \(G\). Thus \(G[S]\) has at most \(\operatorname{ex}(h,H)\) edges.
Count pairs \((e,S)\) where \(e\in E(G)\), \(S\subseteq V(G)\), \(|S|=h\), and both endpoints of \(e\) lie in \(S\). Each edge belongs to exactly \(\binom{n-2}{h-2}\) such subsets, since the other \(h-2\) vertices can be chosen from the remaining \(n-2\). Therefore the number of pairs is \(m\binom{n-2}{h-2}\). On the other hand, each of the \(\binom{n}{h}\) subsets contributes at most \(\operatorname{ex}(h,H)\) pairs. Hence $$ m\binom{n-2}{h-2}\le \binom{n}{h}\operatorname{ex}(h,H). $$ Since \(n\ge h\ge2\), the binomial coefficients being divided by are positive. Dividing and using $$ \frac{\binom{n}{h}}{\binom{n-2}{h-2}} =\frac{n(n-1)}{h(h-1)} =\frac{\binom{n}{2}}{\binom{h}{2}} $$ gives the claimed inequality for \(m\). It holds for every \(H\)-free \(G\), so it holds for the maximum \(\operatorname{ex}(n,H)\) as well. \(\square\)
Worked Example: A Sharp Small Bound for Triangle-Free Graphs
Take \(H=K_3\) and \(n=5\). On three vertices, an \(H\)-free graph has at most two edges: three edges would be a triangle, and two edges can be present without forming one. Thus \(\operatorname{ex}(3,K_3)=2\). The averaging theorem gives $$ \operatorname{ex}(5,K_3)\le 2\frac{\binom{5}{2}}{\binom{3}{2}} =2\frac{10}{3} =\frac{20}{3}. $$ The number of edges is an integer, so this implies \(\operatorname{ex}(5,K_3)\le6\).
To attain six, define \(G\) by \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{13,14,15,23,24,25\}\). The vertices \(\{1,2\}\) have no edge between them, and the vertices \(\{3,4,5\}\) have no edges between them; every edge joins one of the first two vertices to one of the last three. A triangle would need two vertices from one of these sets, but there is no edge between any two vertices in the same set. Therefore \(G\) is triangle-free. Its displayed edge set has six distinct edges, so the upper bound is attained and \(\operatorname{ex}(5,K_3)=6\).
Check: there are \(\binom{5}{3}=10\) three-vertex subsets. Each has at most \(2\) edges, so the total number of edge-subset incidences is at most \(10\cdot2=20\). Each edge lies in \(\binom{3}{1}=3\) three-vertex subsets, giving \(3|E(G)|\le20\), and hence the integer bound \(|E(G)|\le6\). The construction has \(6\) edges and no triangle, verifying equality.
How to Read Extremal Claims
An extremal statement has two logically separate parts. First, an upper-bound argument proves that every graph satisfying the avoidance condition has at most a specified number of edges. Second, a construction gives a graph satisfying the condition with that many edges. Only when both parts agree is the extremal number determined exactly. A construction alone is a lower bound for \(\operatorname{ex}(n,H)\), not an upper bound; an upper bound alone may not be sharp.
It is also important to keep the direction of comparisons straight. If \(F\) is a subgraph of \(H\), avoiding \(F\) is the stronger restriction, so the extremal number for \(F\) is no larger than the one for \(H\). In particular, \(\operatorname{ex}(n,K_2)=0\le \operatorname{ex}(n,K_3)\). The reverse inequality does not follow: a graph can avoid a triangle and still contain many edges.
Common Pitfall
Confusing a subgraph with an induced subgraph. A common incorrect calculation is to inspect only the edges induced on three vertices in a triangle and conclude that it contains no \(P_3\), because those three vertices induce three edges rather than two. That tests for an induced \(P_3\), not an ordinary subgraph \(P_3\). The correction is to select the required edges: in the triangle with edges \(12,23,13\), the vertices \(1,2,3\) together with edges \(12,23\) form a \(P_3\) subgraph. For ordinary forbidden-subgraph extremal numbers, extra edges among the selected vertices do not invalidate the copy.
Check Your Understanding
Use the definitions and arguments above. In each question, distinguish an upper bound from a construction that attains it.
- Why is every graph on \(n\) vertices \(H\)-free when \(n<|V(H)|\)? What is \(\operatorname{ex}(n,H)\) in that case?
- Explain why a \(P_3\)-free graph has maximum degree at most \(1\), and use the handshake lemma to derive an edge bound.
- If \(F\) is a subgraph of \(H\) and \(F\) has at least one edge, which is larger: \(\operatorname{ex}(n,F)\) or \(\operatorname{ex}(n,H)\)? Justify the direction.
- In the averaging theorem, how many \(h\)-vertex subsets contain a fixed edge of an \(n\)-vertex graph?
- Does a graph with six edges and no triangle on five vertices prove \(\operatorname{ex}(5,K_3)=6\) by itself? What additional argument is needed?