Subgraph Comparisons Between Extremal Numbers

Containment Gives an Order on Extremal Numbers

Extremal graph questions ask how many edges a graph can have while avoiding a specified subgraph. When one forbidden graph sits inside another, avoiding the smaller graph is a stronger restriction: it also prevents the larger graph from appearing. This simple observation gives a useful comparison between extremal numbers, even when the two numbers themselves are not known exactly.

All graphs in this tutorial are finite and simple. A copy of a graph $H$ in a graph $G$ means a subgraph isomorphic to $H$. Subgraphs here are not required to be induced: a copy must contain every edge of $H$, but it may have additional edges between its vertices. A graph is H-free if it contains no copy of $H$.

Definition: For a graph $H$ with at least one edge and an integer $n\geq 0$, $\operatorname{ex}(n,H)$ is the maximum number of edges in an $H$-free simple graph on $n$ vertices. The notation $H\subseteq F$ means that $H$ is isomorphic to a subgraph of $F$, not necessarily an induced subgraph.

The maximum in this definition exists: on a fixed set of $n$ vertices there are finitely many simple graphs, and the edgeless graph is $H$-free when $H$ has at least one edge. If $n$ is too small to contain $H$, every $n$-vertex graph is $H$-free, so $\operatorname{ex}(n,H)=\binom{n}{2}$. The same definition and observation apply to any other forbidden graph with at least one edge.

The Subgraph Comparison Theorem

Theorem: If $H\subseteq F$, where $H$ and $F$ are finite simple graphs with at least one edge, then for every integer $n\geq 0$, $$ \operatorname{ex}(n,H)\leq \operatorname{ex}(n,F). $$

Proof. Fix $n\geq 0$. We show that every $H$-free graph on $n$ vertices is also $F$-free. Suppose instead that such a graph $G$ contains a copy of $F$. Since $H\subseteq F$, the vertices and edges of that copy of $F$ include a subgraph isomorphic to $H$. Therefore $G$ contains a copy of $H$, contradicting that $G$ is $H$-free. This proves that the family of $H$-free $n$-vertex graphs is contained in the family of $F$-free $n$-vertex graphs. Every edge count in the first family is consequently at most the maximum edge count in the second family. Taking the maximum over the first family gives $\operatorname{ex}(n,H)\leq\operatorname{ex}(n,F)$. $\square$

The implication concerns the forbidden graphs, not an assertion that an $F$-free graph must be $H$-free. The direction is easy to track by starting with a hypothetical copy of $F$: it supplies a copy of each of its subgraphs, including $H$. Thus an $H$-free graph cannot contain $F$, while an $F$-free graph may still contain $H$.

Corollary: If $H_1\subseteq H_2\subseteq\cdots\subseteq H_k$, with each graph having at least one edge, then for every $n\geq0$, $$ \operatorname{ex}(n,H_1)\leq\operatorname{ex}(n,H_2)\leq\cdots\leq\operatorname{ex}(n,H_k). $$

Proof. Apply the theorem to each containment $H_i\subseteq H_{i+1}$, for $i=1,\dots,k-1$. Each application gives $\operatorname{ex}(n,H_i)\leq\operatorname{ex}(n,H_{i+1})$. Placing these inequalities in order gives the stated chain. If $k=1$, there are no inequalities to apply and the conclusion is just the single term $\operatorname{ex}(n,H_1)$. $\square$

Worked Comparisons

Worked Example: A Chain of Forbidden Cliques

For $r\leq s$, the complete graph $K_r$ is a subgraph of $K_s$: choose any $r$ vertices of $K_s$, which have all $\binom{r}{2}$ edges between them. Consequently, for every $n$,

\operatorname{ex}(n,K_2)\leq\operatorname{ex}(n,K_3)\leq\operatorname{ex}(n,K_4).

Take $n=5$. A $K_2$-free graph has no edges, so $\operatorname{ex}(5,K_2)=0$. Mantel’s theorem gives $\operatorname{ex}(5,K_3)=\lfloor 5^2/4\rfloor=\lfloor25/4\rfloor=6$. This value is attained by $K_{2,3}$, whose parts have sizes $2$ and $3$; every edge joins one vertex from each part, so its edge count is $2\cdot3=6$, and it has no triangle.

The comparison therefore gives $0\leq6\leq\operatorname{ex}(5,K_4)$. The same $K_{2,3}$ graph has no $K_4$, since a clique can use at most one vertex from each part. Hence $\operatorname{ex}(5,K_4)\geq6$, in agreement with the comparison. This argument does not determine the exact value of $\operatorname{ex}(5,K_4)$; the comparison transfers a bound, not automatically an exact answer.

Check: $K_{2,3}$ has five vertices and six edges by the cross-part count $2\cdot3=6$. Its largest clique has size $2$, so it is both triangle-free and $K_4$-free, as required for the two lower-bound checks.

Worked Example: A Path Compared with a Triangle

Let $P_3$ be the path on three vertices, with two edges. It is a subgraph of $K_3$: select any three vertices of the triangle and retain just two of its edges. Therefore

\operatorname{ex}(n,P_3)\leq\operatorname{ex}(n,K_3).

For $n=4$, Mantel’s theorem gives $\operatorname{ex}(4,K_3)=\lfloor4^2/4\rfloor=4$. The graph with $V=\{1,2,3,4\}$ and $E=\{13,14,23,24\}$ is $K_{2,2}$. It has $2\cdot2=4$ edges and is triangle-free, so it attains the bound for $K_3$. It contains a $P_3$, for example the path $1,3,2$, whose two edges are $13$ and $23$. Thus this four-edge example verifies the triangle-free count but is not a $P_3$-free example.

For a lower-bound check on the other extremal number, take $V=\{1,2,3,4\}$ and $E=\{12,34\}$. Each vertex has degree $1$, so there is no two-edge path $P_3$. This graph has $2$ edges, giving $\operatorname{ex}(4,P_3)\geq2$. The comparison supplies the upper bound $\operatorname{ex}(4,P_3)\leq4$; no claim of equality follows from this comparison alone.

Check: The $K_{2,2}$ edge count is $2\cdot2=4$, and $1,3,2$ uses exactly the edges $13$ and $32=23$. The graph with edges $12$ and $34$ has no adjacent pair of edges, so it cannot contain $P_3$.

Worked Example: A 4-Cycle Compared with a Clique

The cycle $C_4$ is a subgraph of $K_4$: order four vertices around the cycle and retain its four cycle edges from the six edges of the complete graph. Hence

\operatorname{ex}(n,C_4)\leq\operatorname{ex}(n,K_4).

For $n=5$, define $G$ by $V=\{1,2,3,4,5\}$, with parts $A=\{1,2,3\}$ and $B=\{4,5\}$, and let $E$ consist of all edges joining $A$ to $B$. Explicitly, $E=\{14,15,24,25,34,35\}$, so $|E|=3\cdot2=6$. The graph has no $K_4$, because any clique has at most one vertex in each of the two parts. Thus $\operatorname{ex}(5,K_4)\geq6$.

However, $G$ contains the 4-cycle $1,4,2,5,1$, using the edges $14,24,25,15$. It is therefore not a $C_4$-free witness. This illustrates the theorem’s direction: a $C_4$-free graph must be $K_4$-free, but a $K_4$-free graph need not be $C_4$-free.

Check: The six listed edges are precisely the $3\cdot2=6$ cross-part pairs. The four edges in the displayed cycle are distinct members of that edge set, and the two parts prevent any four vertices from forming a clique.

How to Use the Comparison

The theorem is useful when one forbidden graph is easier to analyze than another. If $H\subseteq F$ and a known result gives an upper bound for $\operatorname{ex}(n,F)$, then the comparison gives the same upper bound for $\operatorname{ex}(n,H)$. For example, $P_3\subseteq K_3$, so Mantel’s theorem immediately gives $\operatorname{ex}(n,P_3)\leq\lfloor n^2/4\rfloor$. This bound may not be sharp, but it follows without solving the $P_3$-free problem separately.

In the other direction, any $H$-free construction is also $F$-free whenever $H\subseteq F$. Therefore a lower bound for $\operatorname{ex}(n,H)$ also gives a lower bound for $\operatorname{ex}(n,F)$. In the clique example, the triangle-free graph $K_{2,3}$ is automatically $K_4$-free, so its six edges establish a lower bound for both extremal numbers.

Containment alone does not imply strict inequality, equality, or an exact value. The $H$-free class can be a proper subset of the $F$-free class while both classes have a maximum attained at the same edge count. To prove equality or strictness requires additional information about the extremal graphs or sharper bounds.

Common Pitfall: Reversing the Inequality

A common error is to reason that because $H$ is smaller than $F$, forbidding $F$ is the stronger restriction. The theorem’s hypothesis is about which copies contain which: every copy of $F$ contains a copy of $H$, so forbidding $H$ is the stronger restriction. The resulting inequality is $\operatorname{ex}(n,H)\leq\operatorname{ex}(n,F)$, not the reverse.

For a concrete check, take $H=K_3$, $F=K_4$, and $n=4$. Mantel’s theorem gives $\operatorname{ex}(4,K_3)=\lfloor16/4\rfloor=4$. The graph on $\{1,2,3,4\}$ with edges $\{12,13,14,23,24\}$ has five edges and is $K_4$-free, since the edge $34$ is missing. Thus $\operatorname{ex}(4,K_4)\geq5>4=\operatorname{ex}(4,K_3)$, directly ruling out the reversed inequality.

Another pitfall is silently changing “subgraph” to “induced subgraph.” A triangle contains $P_3$ as a subgraph because two of its edges form a path, even though the three vertices induce a triangle rather than an induced $P_3$. Extremal numbers in this comparison use ordinary, non-induced forbidden subgraphs.

Check Your Understanding

For each question, identify the containment direction before comparing the extremal numbers.

If $C_5\subseteq K_5$, which of $\operatorname{ex}(n,C_5)$ and $\operatorname{ex}(n,K_5)$ is at most the other? Explain why.
Explain why a $P_4$-free graph must be $P_3$-free, or give a counterexample.
For $P_3\subseteq K_3$, state an upper bound for $\operatorname{ex}(n,P_3)$ obtained from Mantel’s theorem.
Give a reason that a $K_4$-free graph need not be $C_4$-free.
Does $H\subseteq F$ guarantee $\operatorname{ex}(n,H)<\operatorname{ex}(n,F)$? Explain what the comparison theorem does guarantee.