Common Errors in Extremal Graph Proofs

What an Extremal Proof Must Establish

Extremal graph arguments have two distinct tasks. One is to show that every graph satisfying a restriction has at most a certain number of edges. The other is to show that this bound can actually be attained. Describing an interesting graph does not do both tasks, and obtaining equality in a numerical estimate does not by itself classify all the graphs that attain it. Careful proofs keep the restriction, the bound, the construction, and any equality claim separate.

The assumption that \(F\) has an edge ensures this maximum exists: the edgeless graph on \(n\) vertices is \(F\)-free, so the eligible class is nonempty, and there are only finitely many simple graphs on a fixed \(n\)-vertex set. Without a nonemptiness condition, finiteness alone is not enough. For example, if \(F=K_1\) and \(n\ge1\), every \(n\)-vertex graph contains a copy of \(K_1\), so there is no eligible graph over which to take a maximum.

For a proposed exact value \(M\), a complete extremal proof needs both a universal upper bound and an example attaining it. A classification of equality cases requires an additional argument that identifies every graph for which the upper bound is attained.

Proof. If an \(n\)-vertex graph contains a copy of \(F\), then it contains a copy of \(H\), because \(H\) is a subgraph of \(F\). Taking the contrapositive, every \(H\)-free graph is \(F\)-free. Thus the set of \(H\)-free \(n\)-vertex graphs is contained in the set of \(F\)-free \(n\)-vertex graphs. The maximum number of edges over the first set cannot exceed the maximum over the second, which gives \(\operatorname{ex}(n,H)\le\operatorname{ex}(n,F)\). \(\square\)

Construction Is Not the Same as Extremality

A construction proves a lower bound: it shows that at least one graph satisfying the restriction has a specified number of edges. It does not prove that no other admissible graph has more. To establish an exact extremal number, match the construction with a valid upper bound.

The common error is to find one graph with many edges and silently treat it as a maximizer. The correction is to state exactly what the construction proves, then find an upper bound that applies to every graph satisfying the restriction. In this example, \(C\) proves only \(\operatorname{ex}(5,K_3)\ge5\); \(B\) improves that lower bound, and Mantel’s theorem supplies the matching upper bound.

An Upper Bound Does Not Automatically Prove an Equality Classification

There is a further distinction between proving the value of an extremal number and proving which graphs attain it. The argument for an upper bound may use inequalities. If equality is claimed, the proof must track when those inequalities are equalities and show what that forces about the graph.

Proof. Let \(G\) be triangle-free, with \(n\) vertices and \(m\) edges. For each edge \(uv\), the neighborhoods \(N(u)\) and \(N(v)\) are disjoint: a common neighbor would form a triangle with \(u\) and \(v\). Therefore \(\deg(u)+\deg(v)\le n\). Summing over all edges, each vertex \(v\) contributes \(\deg(v)\) once for each incident edge, so \(\sum_{v\in V(G)}\deg(v)^2=\sum_{uv\in E(G)}(\deg(u)+\deg(v))\le nm\). Also, \(\sum_v\deg(v)=2m\) by the handshake lemma, and Cauchy–Schwarz gives \((2m)^2\le n\sum_v\deg(v)^2\). Combining the inequalities yields \(4m^2\le n^2m\). If \(m=0\), the claimed upper bound holds; if \(m>0\), divide by \(4m\) to obtain \(m\le n^2/4\).

Now suppose \(m=n^2/4\). Both inequalities in the chain must be equalities. Equality in Cauchy–Schwarz implies that all \(n\) degrees are equal; their sum is \(2m=n^2/2\), so every degree is \(n/2\). Choose any edge \(uv\), which exists because \(m>0\). Its endpoint neighborhoods are disjoint and each has size \(n/2\), so together they contain all \(n\) vertices. Each neighborhood is independent: an edge between two neighbors of \(u\), for instance, would form a triangle with \(u\). Thus \(N(u)\) and \(N(v)\) are two independent parts. Each vertex has degree \(n/2\), the size of the opposite part, so every possible edge between the parts is present. Hence \(G\cong K_{n/2,n/2}\).

Conversely, \(K_{n/2,n/2}\) is triangle-free and has \((n/2)(n/2)=n^2/4\) edges. It attains the bound and is an equality case. This proves both directions of the classification. \(\square\)

Keep Forbidden-Subgraph Implications in the Right Direction

Words such as “contains” and “forbids” can reverse an implication if the graphs are not compared carefully. If \(H\) is a subgraph of \(F\), then forbidding \(H\) is at least as restrictive as forbidding \(F\): every \(H\)-free graph is \(F\)-free. But an \(F\)-free graph need not be \(H\)-free. This is why the proposition gives \(\operatorname{ex}(n,H)\le\operatorname{ex}(n,F)\), not the reverse inequality.

A Degree Bound May Be Too Weak to Prove Sharpness

A degree estimate can give a correct upper bound and still fail to identify the extremal number. For instance, the universal bound \(\deg(v)\le n-1\), together with the handshake lemma, gives \(2m\le n(n-1)\). For a forbidden-subgraph problem, a sharper degree estimate may be available, but it must still be strong enough to match a construction if the goal is an exact value.

A Reliable Checklist

When reviewing an extremal proof, separate the claims it must support. First confirm that the extremal number is defined for a nonempty class of eligible graphs. Then check that each construction satisfies the forbidden-subgraph condition and count its edges. Treat that count as a lower bound until a universal upper bound matches it. If the proof claims an equality characterization, follow every inequality through its equality conditions and prove that they force the stated structure. Finally, when comparing forbidden graphs, verify the implication on the graph classes before comparing their extremal numbers.

These checks are useful because a proof can contain correct calculations yet reach an unsupported conclusion. A graph may be admissible without being extremal; an upper bound may be correct without being sharp; and an extremal value may be proved without classifying all extremal graphs. Identifying exactly which claim has been established is the first step toward repairing the argument.