From Constructions to Extremal Bounds
For a fixed forbidden graph, an extremal problem asks how many edges a graph can have without containing that graph. A construction answers one half of the problem: if we exhibit a graph with \(n\) vertices, \(m\) edges, and no forbidden copy, then the extremal number is at least \(m\). To prove that \(m\) is the exact answer, we also need an upper bound showing that every eligible graph has at most \(m\) edges. This tutorial develops both steps through explicit constructions and small counting arguments.
All graphs are finite and simple. A subgraph may be formed by deleting vertices or edges; it need not be induced. In particular, a graph contains \(H\) as a subgraph if some vertices and some of the edges between them form a copy of \(H\), whether or not other edges are present.
The condition that \(H\) has at least one edge matters. With this condition, the empty graph on \(n\) vertices is \(H\)-free for every \(n\), so the set of eligible graphs is nonempty. There are only finitely many simple graphs on a fixed \(n\)-vertex set, so a largest edge count exists. If \(H\) were edgeless, even a one-vertex graph could contain it, and there might be no eligible graphs at all.
These inequalities have different jobs. A construction cannot by itself rule out a denser graph, and an upper bound does not show that its edge limit can be attained. A sound solution checks both the forbidden-subgraph condition and the edge count of the proposed construction, then supplies a separate argument for the upper bound if an exact value is claimed.
A Counting Tool for \(C_4\)-Free Graphs
We will use two elementary counting facts. For a vertex \(v\), its degree \(\deg(v)\) is the number of its neighbors. The degree sum counts each edge once at each endpoint, giving the handshaking identity below. We include the count to make explicit what is being measured.
Proof. Count incidences \((v,e)\) in which vertex \(v\) is an endpoint of edge \(e\). Counting by vertices gives \(\sum_{v\in V}\deg(v)\). Every edge has exactly two distinct endpoints in a simple graph, so counting by edges gives \(2|E|\). Both counts enumerate the same incidences, proving the identity. If \(V\) is empty, both sums are \(0\), so the identity still holds. \(\square\)
Proof. For each vertex \(v\), the quantity \(\binom{\deg(v)}{2}\) counts unordered pairs of distinct neighbors of \(v\). Thus the sum on the left counts pairs of vertices that have a common neighbor, with one count for each common neighbor. If distinct vertices \(u,w\) had two distinct common neighbors \(x,y\), then \(u,x,w,y,u\) would be a cycle of length four: the vertices are distinct, and each consecutive pair is joined by an edge. This contradicts that \(G\) is \(C_4\)-free. Therefore each unordered pair of vertices is counted at most once. There are \(\binom{|V(G)|}{2}\) such pairs, proving the inequality. When there are fewer than two vertices, both sides are \(0\). \(\square\)
The lemma illustrates a general counting strategy: count a local feature in two ways, then use the forbidden-subgraph condition to limit how often it can occur. Here, the local feature is a pair of neighbors with a specified common neighbor. The lemma is useful only when the graph is \(C_4\)-free; without that hypothesis, one pair might have multiple common neighbors.
Worked Constructions and Bounds
Worked Example: A Cycle Gives a Lower Bound for \(C_4\)
Let \(n=7\), and take \(G=C_7\), with vertex set \(V=\{1,2,3,4,5,6,7\}\) and edge set \(E=\{12,23,34,45,56,67,71\}\). We claim this construction gives a lower bound for \(\operatorname{ex}(7,C_4)\).
The graph has seven listed edges, so \(|E|=7\). Its only cycle is the full 7-cycle: at every vertex there are exactly two incident edges, and following a cycle from any vertex forces continuing around the entire cycle before returning to the start. Consequently it has no cycle of length four and is \(C_4\)-free. This verifies both the edge count and the forbidden-subgraph condition, so \(\operatorname{ex}(7,C_4)\ge 7\).
Check: every vertex has degree \(2\), so the degree sum is \(7\cdot2=14\). The handshaking identity gives \(2|E|=2\cdot7=14\), agreeing with the direct count of seven edges. This is a lower bound only: the construction does not prove that every \(C_4\)-free graph on seven vertices has at most seven edges.
Worked Example: An Exact Value for Five Vertices
We determine \(\operatorname{ex}(5,C_4)\). For a lower bound, let \(G\) have vertex set \(V=\{x,a,b,c,d\}\) and edge set \(E=\{xa,xb,ab,xc,xd,cd\}\). This consists of two triangles sharing only \(x\).
There are six listed edges. A cycle that uses vertices from both triangles would have to pass through \(x\) twice before closing, which is not allowed in a cycle. Within either triangle, the only cycle has length three. Thus \(G\) has no 4-cycle, and \(\operatorname{ex}(5,C_4)\ge6\).
For the upper bound, let \(F\) be any \(C_4\)-free graph on five vertices, and write \(m=|E(F)|\). Suppose, for contradiction, that \(m\ge7\). The degree-sum lemma gives \(\sum_{v\in V(F)}\deg(v)=2m\ge14\). Each degree is at most \(4\), because there are only four other vertices.
Among five nonnegative integer degrees with sum at least \(14\), each at most \(4\), the sum of the quantities \(\binom{\deg(v)}{2}\) is at least \(13\). To verify this bound, first reduce degrees if necessary until their sum is \(14\); this cannot increase any \(\binom{\deg(v)}{2}\). At fixed sum, if two degrees \(a,b\) satisfy \(a\ge b+2\), replacing them by \(a-1,b+1\) changes their binomial sum by \[ \binom{a}{2}+\binom{b}{2}-\binom{a-1}{2}-\binom{b+1}{2}=a-b-1\ge1. \] So balancing the degrees minimizes the sum. Five degrees summing to \(14\) as evenly as possible are \(3,3,3,3,2\), and their binomial sum is \(4\binom{3}{2}+\binom{2}{2}=4\cdot3+1=13\).
But the common-neighbor lemma gives \(\sum_v\binom{\deg(v)}{2}\le\binom{5}{2}=10\), contradicting the lower bound \(13\). Hence \(m\le6\). The construction attains six edges, so \(\operatorname{ex}(5,C_4)=6\).
Check: in the construction, \(\deg(x)=4\) and \(\deg(a)=\deg(b)=\deg(c)=\deg(d)=2\). Their sum is \(4+4\cdot2=12=2\cdot6\), as required. Also, the four leaves contribute \(4\binom{2}{2}=4\), while \(x\) contributes \(\binom{4}{2}=6\), for a total of \(10=\binom{5}{2}\). No pair of vertices has more than one common neighbor.
Worked Example: Two Triangles Give a \(K_4\)-Free Construction
For another forbidden graph, consider \(H=K_4\) and \(n=6\). Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,23,31,45,56,64\}\). Thus \(G\) is the disjoint union of two triangles.
There are three edges in each triangle, so \(|E|=3+3=6\). Every connected component has only three vertices; therefore no four vertices can form a \(K_4\) subgraph. The construction is \(K_4\)-free, and it proves \(\operatorname{ex}(6,K_4)\ge6\). This statement is a lower bound, not an exact evaluation.
Independent check: all six vertices have degree \(2\), so the degree sum is \(6\cdot2=12\). The edge count gives \(2|E|=2\cdot6=12\), agreeing with the handshaking identity. The two components have disjoint vertex sets, so no edge or \(K_4\) can be assembled by combining edges from the separate triangles.
How to Build and Audit an Extremal Argument
Specify its vertex set and edge set, or give an unambiguous construction rule. Count its edges directly.
Use the actual definition of subgraph. Identify why no selection of vertices and edges can form the forbidden graph.
The construction proves \(\operatorname{ex}(n,H)\ge |E(G)|\). Do not call this an exact value unless there is also a matching upper bound.
Count degrees, neighbor pairs, or another feature constrained by \(H\)-freeness. State the hypothesis that makes the count valid.
Construction choices can depend strongly on the forbidden graph. A cycle is a useful \(C_4\)-free example when its length is not four; two small cliques on separate vertex sets give a simple \(K_4\)-free example. These are starting points, not universal recipes. A construction valid for one \(H\) may contain another forbidden graph, and a construction that works for one value of \(n\) may not extend in the same way to all \(n\).
Common Pitfalls
Confusing induced and ordinary subgraphs. A triangle contains a path on three vertices as an ordinary subgraph: select two of its edges and omit the third. It does not contain that path as an induced subgraph, because the third edge remains among the selected vertices. Extremal numbers here forbid ordinary subgraphs, so extra edges do not prevent a copy. Always check which notion is being used.
Using a lower bound as if it were an equality. The \(C_7\) example proves \(\operatorname{ex}(7,C_4)\ge7\), not \(\operatorname{ex}(7,C_4)=7\). To claim equality, one must also rule out every \(C_4\)-free graph with more than seven edges. The five-vertex example becomes exact only because its construction is paired with a valid upper-bound proof.
Counting the same feature incorrectly. In the common-neighbor argument, \(\binom{\deg(v)}{2}\) counts pairs of neighbors of one fixed vertex \(v\). The sum counts a vertex pair once for each common neighbor. The \(C_4\)-free assumption limits this multiplicity to one; it does not say that every pair is counted. The resulting inequality is “at most,” not necessarily equality.
Check Your Understanding
For each question, distinguish the construction claim from any upper-bound claim.
- Let \(G\) be the cycle on six vertices, with edges \(12,23,34,45,56,61\). Explain why this gives a lower bound for \(\operatorname{ex}(6,C_4)\), and state the bound.
- Why does the definition of \(\operatorname{ex}(n,H)\) above require \(H\) to have at least one edge?
- In a \(C_4\)-free graph, explain why two vertices cannot have two distinct common neighbors.
- A graph on five vertices has seven edges and is claimed to be \(C_4\)-free. Use the common-neighbor count to identify the contradiction.
- Give an example of a graph that contains a three-vertex path as a subgraph but not as an induced subgraph. Explain why that distinction matters here.