The Sharp Edge Bound for Triangle-Free Graphs
Extremal graph theory asks how many edges a graph can have while avoiding a specified subgraph. For the forbidden subgraph consisting of a triangle, the extremal number has a particularly simple exact formula. The result identifies both a ceiling that every triangle-free graph must respect and a construction that reaches that ceiling.
Throughout, graphs are finite and simple. A triangle is a cycle of length three, and a graph is triangle-free if it contains no triangle. For a nonnegative integer \(n\), let \(\operatorname{ex}(n,K_3)\) denote the maximum number of edges among all triangle-free graphs with \(n\) vertices. The maximum exists because there are only finitely many simple graphs on a fixed number of vertices.
A complete bipartite graph has its vertices divided into two parts, with every possible edge between the parts and no edges within either part. It is triangle-free: along every edge a walk switches parts, so a cycle that returns to its starting part must have even length. To count its edges, if the part sizes are \(a\) and \(b\), each of the \(a\) vertices in the first part is joined to all \(b\) vertices in the second, giving \(ab\) edges.
For a fixed total \(n=a+b\), the product \(ab=a(n-a)\) is largest when the two part sizes are as close as possible. Indeed, $$ a(n-a)=\frac{n^2}{4}-\left(a-\frac n2\right)^2. $$ Since \(a\) is an integer, the closest choices to \(n/2\) are \(\lfloor n/2\rfloor\) and \(\lceil n/2\rceil\). Their product is \(\lfloor n^2/4\rfloor\): for \(n=2k\), it is \(k^2\), while for \(n=2k+1\), it is \(k(k+1)\). This establishes the edge count of the proposed construction. The theorem's other claim—that no triangle-free graph has more edges—requires proof.
Proof by Deleting the Endpoints of an Edge
The proof uses induction on the number of vertices. Its key observation concerns the two endpoints of any edge: in a triangle-free graph they cannot have a common neighbor. We first prove the upper bound, then verify that the balanced construction reaches it.
Proof. Let \(N(u)\) and \(N(v)\) be the sets of vertices adjacent to \(u\) and \(v\), respectively. Neither set contains a common vertex: if \(w\) belonged to both, then \(u,v,w\) would form a triangle. Also \(u\in N(v)\) but \(u\notin N(u)\), and \(v\in N(u)\) but \(v\notin N(v)\), because the graph is simple. Thus \(N(u)\) and \(N(v)\) are disjoint subsets of \(V(G)\). Their sizes are the respective degrees, so $$ \deg(u)+\deg(v)=|N(u)|+|N(v)|=|N(u)\cup N(v)|\le |V(G)|. $$ \(\square\)
Proof. We use strong induction on \(n\), meaning that when proving the claim for order \(n\), we may use it for every smaller nonnegative order. For \(n=0\) or \(n=1\), a simple graph has no edges, and \(\lfloor n^2/4\rfloor=0\), so the claim holds.
Now let \(n\ge2\) and assume the claim holds for all smaller orders. If \(G\) has no edges, its edge count is zero and satisfies the bound. Otherwise choose an edge \(uv\). The lemma gives \(\deg(u)+\deg(v)\le n\). Delete both endpoints and all edges incident to them, leaving the graph \(H=G-\{u,v\}\). It has \(n-2\) vertices and is triangle-free, since deleting vertices cannot create a triangle. The edge \(uv\) is counted in both degrees; every other edge incident to either endpoint is counted once. There is no edge counted as incident to both endpoints besides \(uv\), because the graph is simple. Consequently the number of edges deleted is exactly \(\deg(u)+\deg(v)-1\), and $$ |E(G)|=|E(H)|+\deg(u)+\deg(v)-1 \le \left\lfloor\frac{(n-2)^2}{4}\right\rfloor+n-1, $$ where the inequality uses the induction hypothesis on \(H\) and the lemma.
It remains to evaluate the right-hand side. If \(n=2k\), then $$ \left\lfloor\frac{(n-2)^2}{4}\right\rfloor+n-1 =(k-1)^2+2k-1 =k^2 =\left\lfloor\frac{n^2}{4}\right\rfloor. $$ If \(n=2k+1\), then $$ \left\lfloor\frac{(n-2)^2}{4}\right\rfloor+n-1 =k(k-1)+2k =k(k+1) =\left\lfloor\frac{n^2}{4}\right\rfloor. $$ Thus the bound holds for \(n\), completing the induction. \(\square\)
For the matching lower bound, take the complete bipartite graph with parts of sizes \(\lfloor n/2\rfloor\) and \(\lceil n/2\rceil\). As noted above, it is triangle-free, and its edge count is the product of those sizes, namely \(\lfloor n^2/4\rfloor\). Therefore no smaller upper bound can hold, and the theorem follows.
Applying the Formula
Worked Example: Eight Vertices
Find the maximum number of edges in a triangle-free graph on eight vertices, and give a graph attaining it.
Substitute \(n=8\) into Mantel's formula: $$ \left\lfloor\frac{8^2}{4}\right\rfloor =\left\lfloor\frac{64}{4}\right\rfloor =16. $$ Thus every triangle-free graph on eight vertices has at most sixteen edges.
For a construction, let \(V=\{1,2,3,4,5,6,7,8\}\), with parts \(X=\{1,2,3,4\}\) and \(Y=\{5,6,7,8\}\), and set \(E=\{ij:i\in X,\ j\in Y\}\). Every edge crosses between the two parts, so a triangle cannot occur. There are four choices of endpoint in \(X\) and four in \(Y\), giving \(4\cdot4=16\) edges.
Check: the construction has \(16\) edges by the direct cross-pair count, and the theorem bounds every such graph by \(16\). It therefore attains the maximum.
Worked Example: Seven Vertices and an Unbalanced Construction
Calculate the maximum for seven vertices, then compare a balanced construction with an unbalanced complete bipartite graph.
The formula gives $$ \left\lfloor\frac{7^2}{4}\right\rfloor =\left\lfloor\frac{49}{4}\right\rfloor =12, $$ since \(49/4=12.25\) and its floor is \(12\). So twelve is an upper bound.
Let \(V=\{1,2,3,4,5,6,7\}\). Taking parts \(X=\{1,2,3\}\) and \(Y=\{4,5,6,7\}\), with \(E=\{ij:i\in X,\ j\in Y\}\), gives a triangle-free graph with \(3\cdot4=12\) edges. The balanced construction therefore attains the bound.
For comparison, take parts \(X'=\{1,2\}\) and \(Y'=\{3,4,5,6,7\}\), again including every edge between the parts and none within either part. This graph is triangle-free and has \(2\cdot5=10\) edges. Both graphs have seven vertices, but only the balanced one reaches twelve.
Check: the first construction has \(3\cdot4=12\) cross-part edges, matching the computed upper bound of \(12\). The second has \(2\cdot5=10\) cross-part edges, which is below \(12\). Both counts come from the number of choices of one endpoint in each part.
Worked Example: A Six-Cycle Does Not Reach the Bound
Consider the graph \(G\) with \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,61\}\). Determine whether it is triangle-free, count its edges, and compare with the maximum possible count on six vertices.
The listed edges form the cycle \(1,2,3,4,5,6,1\). Each vertex is adjacent only to its two neighbors on this cycle, and those two neighbors are not adjacent to one another. Hence no three vertices form a triangle. The edge list contains six distinct edges, so \(|E(G)|=6\).
For six vertices, Mantel's bound is $$ \left\lfloor\frac{6^2}{4}\right\rfloor =\left\lfloor\frac{36}{4}\right\rfloor =9. $$ A graph that attains it has \(V=\{1,2,3,4,5,6\}\), parts \(\{1,2,3\}\) and \(\{4,5,6\}\), and all nine edges between those parts. Its count is \(3\cdot3=9\).
Check: the cycle has six listed edges, while the complete bipartite construction has \(3\cdot3=9\) edges. The cycle is triangle-free but is not extremal; being triangle-free alone does not guarantee the largest possible edge count.
Interpreting the Bound and Avoiding a Common Error
Mantel's theorem gives an exact answer to an extremal question, not a claim that every triangle-free graph has the same number of edges. Some such graphs can have far fewer edges, including graphs with no edges at all. The balanced complete bipartite construction shows that the upper bound is sharp, while the induction proves that no triangle-free graph can exceed it.
The dependence on parity is useful when calculating the bound. If \(n=2k\), it is \(k^2\). If \(n=2k+1\), it is \(k(k+1)\). The odd case is a product of two adjacent integers because the parts cannot have exactly equal integer sizes.
Common mistake: forgetting to take the floor. For seven vertices, writing \(n^2/4=49/4=12.25\) and concluding that a triangle-free graph may have \(12.25\) edges is not a valid edge count: the number of edges must be an integer. The theorem gives \(\lfloor49/4\rfloor=12\), and the balanced construction with parts of sizes three and four has \(3\cdot4=12\) edges. The floor is essential whenever \(n\) is odd.
Another useful distinction is between an upper bound and a witness. The formula alone says that no graph in the class has more than the stated number of edges; the complete bipartite construction verifies that the bound is attained. Both parts are needed to establish the exact maximum.
Check Your Understanding
Use the theorem and its proof to answer the following questions.
- What is the maximum number of edges in a triangle-free graph on ten vertices? State the balanced complete bipartite construction that attains it.
- For nine vertices, calculate the bound and give the two part sizes of a construction that reaches it.
- In the induction proof, why can \(N(u)\) and \(N(v)\) not contain a common vertex when \(uv\) is an edge?
- When the endpoints \(u\) and \(v\) of an edge are deleted, why is the number of deleted edges \(\deg(u)+\deg(v)-1\), rather than \(\deg(u)+\deg(v)\)?
- A triangle-free graph has seven vertices and ten edges. Does Mantel's theorem imply that it is extremal? Explain what the theorem does and does not establish.