Extremal Numbers by Finite Search
Extremal graph theory asks how many edges a graph can have while avoiding a specified forbidden subgraph. General theorems can give elegant answers, but for a small fixed number of vertices there is another useful method: list every possible edge set, test it, and compare the edge counts of the graphs that pass. The method is finite and exact. Its reliability depends on encoding all candidates and checking the forbidden condition without omissions.
Throughout, graphs are finite and simple. For a fixed forbidden graph \(F\), a graph \(G\) contains \(F\) as a subgraph if there is an injective map from \(V(F)\) to \(V(G)\) that sends every edge of \(F\) to an edge of \(G\). The map need not preserve nonedges: extra edges among the image vertices do not prevent a subgraph copy. An induced copy has the additional requirement that nonedges of \(F\) map to nonedges of \(G\).
To search on the labelled vertex set \(\{1,\ldots,n\}\), first list its possible edges in a fixed order. There are \(\binom n2\) such pairs, and every subset of those pairs is the edge set of exactly one simple graph. Thus there are \(2^{\binom n2}\) candidates. A binary edge mask records whether each pair is present. For each candidate, test every injection of \(V(F)\) into \(\{1,\ldots,n\}\); the candidate contains \(F\) exactly when at least one injection preserves every edge of \(F\).
Fix an ordering of all \(\binom n2\) unordered vertex pairs.
Run through all \(2^{\binom n2}\) subsets of the listed pairs, including the empty subset.
For each candidate, check all injections from \(V(F)\) into its vertex set and record whether any sends every edge of \(F\) to an edge of the candidate.
Among candidates that pass, retain the largest number of present edges and record a graph attaining it.
Why the Search Is Exhaustive
Proof. Let \(P\) be the set of all unordered pairs of distinct vertices in \(\{1,\ldots,n\}\). A simple graph on this vertex set has no loops or multiple edges, so its edge set is one subset \(S\subseteq P\). Conversely, each subset \(S\subseteq P\) defines one simple graph with vertex set \(\{1,\ldots,n\}\) and edge set \(S\). These two assignments reverse each other, so the subsets and labelled graphs are in one-to-one correspondence. This also covers \(n=0\) or \(n=1\), when \(P\) is empty and there is one subset, the empty set.
For a candidate \(G\), if an injection sends every edge of \(F\) to an edge of \(G\), its image vertices and those image edges form a subgraph copy of \(F\); any additional edges of \(G\) can be omitted from that subgraph. Conversely, if \(G\) contains a subgraph copy of \(F\), the correspondence of vertices in that copy defines an injection that sends every edge of \(F\) to an edge of \(G\). Therefore the test rejects precisely the candidates containing \(F\). If there is no injection, as when \(|V(F)|>|V(G)|\), the test finds no copy, as required. \(\square\)
Proof. By the proposition, every labelled simple graph on \(n\) vertices occurs in the search, and the test retains exactly the graphs containing no subgraph copy of \(F\). The largest retained edge count is therefore at least the edge count of every \(n\)-vertex \(F\)-free graph. It is also the edge count of a retained graph, so it cannot exceed the largest edge count among such graphs. The two quantities are equal. Relabelling vertices does not change the number of edges or whether a copy of \(F\) exists, so considering labelled graphs does not change the extremal number. \(\square\)
Small Searches Worked in Full
Worked Example: Avoiding a Triangle on Three Vertices
Find \(\operatorname{ex}(3,K_3)\). Label the vertices \(1,2,3\), and order the possible edges as \(12,13,23\). Each mask is the subset of these three pairs that is present. The eight masks, grouped by their number \(m\) of edges, are:
| Number of edges \(m\) | Candidate edge sets | Contains \(K_3\)? |
|---|---|---|
| 0 | \(\varnothing\) | No |
| 1 | \(\{12\},\{13\},\{23\}\) | No for all three |
| 2 | \(\{12,13\},\{12,23\},\{13,23\}\) | No for all three |
| 3 | \(\{12,13,23\}\) | Yes |
There are \(1+3+3+1=8=2^3\) candidates, because the three possible edges can each be absent or present. Only the candidate with all three edges contains a triangle. Thus every accepted candidate has at most two edges. The graph with \(V=\{1,2,3\}\) and \(E=\{12,13\}\) has two edges and no triangle, so the upper bound is attained.
Check: the number of candidates is \(2^3=8\), and the table has \(1+3+3+1=8\) entries by edge count. The maximum accepted edge count is \(2\), giving \(\operatorname{ex}(3,K_3)=2\).
Worked Example: Avoiding \(K_4\) on Four Vertices
Find \(\operatorname{ex}(4,K_4)\). There are \(\binom42=6\) possible edges, so the search has \(2^6=64\) candidates. A copy of \(K_4\) must use four distinct vertices and requires all six pairs among them. On this vertex set, that happens exactly when the candidate is the complete graph \(K_4\).
Grouped by edge count \(m\), the total numbers of candidates are \(\binom6m\): for \(m=0,1,2,3,4,5,6\), these are \(1,6,15,20,15,6,1\). Only the one candidate with \(m=6\) is rejected. Hence the accepted counts in those classes are \(1,6,15,20,15,6,0\), respectively. Every accepted graph has at most five edges.
The graph on \(V=\{1,2,3,4\}\) with \(E=\{12,13,14,23,24\}\) has five edges: it is \(K_4\) with edge \(34\) omitted. It is \(K_4\)-free because any copy on four vertices would require the missing pair \(34\).
Check: the total number of candidates is \(1+6+15+20+15+6+1=64=2^6\). The accepted count is \(1+6+15+20+15+6=63\), with the remaining candidate the complete graph. The construction attains five edges, so \(\operatorname{ex}(4,K_4)=5\).
Worked Example: Avoiding a Triangle on Four Vertices
Find \(\operatorname{ex}(4,K_3)\) by searching all edge subsets. Write \(V=\{1,2,3,4\}\). There are \(\binom42=6\) possible edges, hence \(2^6=64\) labelled graphs. The total candidate counts by edge number \(m=0,1,\ldots,6\) are \(\binom6m\), namely \(1,6,15,20,15,6,1\).
Now count the rejected graphs in each class. With zero, one, or two edges, a triangle is impossible. With three edges, a rejected graph must consist of the three edges of a triangle; there are four choices, one for each three-vertex subset of \(V\). Thus \(4\) of the \(20\) candidates with three edges are rejected.
With four edges, exactly three candidates are triangle-free: the three labelled 4-cycles. To justify that classification, a triangle-free graph on four vertices with four edges cannot have a vertex of degree \(3\): its three neighbors would need to have no edges between them, leaving at most the three edges incident to that vertex. Therefore all degrees are at most \(2\). The degree sum is \(2m=8\), so all four degrees equal \(2\). A simple graph in which all four vertices have degree \(2\) is a 4-cycle. There are three such cycles on the four labelled vertices, one for each way to choose the two pairs of opposite vertices. Since there are \(15\) four-edge candidates in total, \(15-3=12\) are rejected.
With five edges, each candidate is \(K_4\) with one of its six possible edges omitted. It still contains a triangle: the two endpoints of the omitted edge are each adjacent to the other two vertices, and the edge between those other two vertices is present. All six candidates are rejected. With six edges, the candidate is \(K_4\), which contains triangles, so one candidate is rejected.
| Edges \(m\) | All candidates | Rejected: contains \(K_3\) | Accepted: \(K_3\)-free |
|---|---|---|---|
| 0 | 1 | 0 | 1 |
| 1 | 6 | 0 | 6 |
| 2 | 15 | 0 | 15 |
| 3 | 20 | 4 | 16 |
| 4 | 15 | 12 | 3 |
| 5 | 6 | 6 | 0 |
| 6 | 1 | 1 | 0 |
| Total | 64 | 23 | 41 |
The largest edge count in an accepted class is \(4\). It is attained by the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,14,32,34\}\). Its edges all join the parts \(\{1,3\}\) and \(\{2,4\}\). A triangle would require three pairwise adjacent vertices, but among any three vertices at least two lie in the same part, and there is no edge within either part. Thus this construction is triangle-free.
Check: the rejected counts sum to \(0+0+0+4+12+6+1=23\). The accepted counts sum to \(1+6+15+16+3+0+0=41\), and \(23+41=64\), the full number of candidates. The construction has four edges, so the search and construction together give \(\operatorname{ex}(4,K_3)=4\).
Reading and Checking a Search Certificate
A finite search gives two different kinds of evidence. The complete enumeration gives an upper bound: no accepted candidate has more than the reported number of edges. A construction gives a lower bound: at least one accepted candidate has that many edges. Both are needed to certify an extremal number. A table of computer output without a stated encoding or test is difficult to audit; a construction without an exhaustive upper bound does not establish optimality.
For larger fixed vertex sets, one can reduce repeated work by grouping graphs that differ only by a relabelling, but that reduction requires a correct method for identifying isomorphic graphs. It is not necessary for correctness: the direct search over all labelled graphs already includes every graph up to relabelling. Grouping candidates by edge count is also a useful independent check, since the total number in the class with \(m\) edges must be \(\binom{\binom n2}{m}\).
Common Counting Pitfall
When reporting rejected candidates by edge count, include every class, including the class with the largest possible number of edges. In the four-vertex triangle search, writing \(4+12+6=22\) counts the rejected graphs with three, four, and five edges but omits the one rejected graph with six edges. The corrected total is \(4+12+6+1=23\). Comparing this with the \(64\) candidates gives \(64-23=41\) accepted graphs, which agrees with the accepted-class sum \(1+6+15+16+3=41\).
Other checks catch different errors: the counts in each row must satisfy “accepted plus rejected equals all candidates,” and the row totals must sum to \(2^{\binom n2}\). These checks do not replace the forbidden-subgraph test, but they can reveal a missing class or an arithmetic mistake before the extremal conclusion is drawn.
Check Your Understanding
Use the edge-subset method and justify each conclusion with either a complete small count or a construction and an upper bound.
- How many labelled simple graphs are there on five vertices? Explain why the answer is a power of two.
- For the four-vertex triangle search, why does a five-edge candidate necessarily contain a triangle?
- Explain why the three four-edge triangle-free graphs on four vertices are precisely the labelled 4-cycles.
- What extra condition must an injection satisfy when testing for an induced copy rather than an ordinary subgraph copy?
- Why does finding one \(F\)-free graph with \(r\) edges prove only a lower bound on \(\operatorname{ex}(n,F)\), not an upper bound?