Equality Cases in Mantel's Theorem

From an Edge Bound to a Structural Conclusion

Mantel’s theorem bounds the number of edges in a triangle-free graph on \(n\) vertices by \(\lfloor n^2/4\rfloor\). Equality says more than that the edge count is large: it determines the entire graph. The extremal example is the complete bipartite graph whose two parts have sizes as equal as possible. Here we trace the equality conditions in the degree argument and show why they force precisely that structure.

All graphs below are finite and simple. The balanced complete bipartite graph has \(\lfloor n^2/4\rfloor\) edges: its number of edges is the product of its part sizes. We will prove that a triangle-free graph on \(n\) vertices has that many edges if and only if it is this graph, up to the names of its vertices. The empty graph on zero vertices and the single isolated vertex are included: they are \(K_{0,0}\) and \(K_{0,1}\), respectively.

The Bound and Its Degree Conditions

For an edge \(uv\) in a triangle-free graph, the neighborhoods \(N(u)\) and \(N(v)\) are disjoint. Otherwise a common neighbor would form a triangle with \(u\) and \(v\). Therefore \(\deg(u)+\deg(v)\le n\). Summing this inequality over edges and counting each vertex degree once for each incident edge gives the degree identity used in the proof below.

Proof. Write \(m=|E(G)|\). If \(n=0\), then \(m=0\), so the assertion holds. Suppose \(n\ge1\). The degree sum over edges satisfies \(\sum_{v\in V(G)}\deg(v)^2=\sum_{uv\in E(G)}(\deg(u)+\deg(v))\le mn\). Also, since the sum of the degrees is \(2m\), nonnegativity of the sum of squared deviations from their mean gives \(\sum_v\deg(v)^2\ge (2m)^2/n\). If \(m>0\), combining these inequalities yields \(4m^2/n\le mn\), hence \(m\le n^2/4\); since \(m\) is an integer, \(m\le\lfloor n^2/4\rfloor\). If \(m=0\), the same conclusion holds directly. \(\square\)

For an equality proof, it matters whether \(n\) is even or odd. When \(n\) is even, attaining the bound makes the real-valued inequality \(m\le n^2/4\) an equality, so both inequalities in the proof must be equalities. When \(n\) is odd, \(\lfloor n^2/4\rfloor<n^2/4\); the same observation alone does not force equality in those inequalities. We need the fact that degrees are integers.

Proof. First suppose \(n\) is even. Then \(m=n^2/4\). The bound’s proof gives \((2m)^2/n\le\sum_v\deg(v)^2\le mn\). Substituting \(m=n^2/4\), both endpoints equal \(n^3/4\). Thus \(\sum_v\deg(v)^2=mn\). But \(\sum_{uv\in E(G)}(\deg(u)+\deg(v))\) is a sum of \(m\) terms, each at most \(n\). Its value is \(mn\), so every term equals \(n\).

Now suppose \(n=2k+1\) is odd. Since \(n\ge2\), we have \(k\ge1\), and \(m=k(k+1)\). The degrees are integers with sum \(2m=2k(k+1)\). Among integer lists of this length and sum, the sum of squares is minimized when all entries differ by at most one: if two entries \(x,y\) satisfy \(x\ge y+2\), replacing them by \(x-1,y+1\) keeps their sum fixed and reduces their square sum by \(2(x-y)-2>0\). The average degree is \(2k(k+1)/(2k+1)=k+k/(2k+1)\), so a minimizing list has \(k\) entries equal to \(k+1\) and \(k+1\) entries equal to \(k\). Its square sum is \(k(k+1)^2+(k+1)k^2=k(k+1)(2k+1)=mn\). Consequently \(\sum_v\deg(v)^2\ge mn\). The edge inequality already gives \(\sum_v\deg(v)^2\le mn\), so equality holds. As in the even case, the sum of the \(m\) edge terms, each at most \(n\), equals \(mn\); every edge term must equal \(n\). \(\square\)

Equality Characterizes the Balanced Complete Bipartite Graph

Proof. If \(n=0\) or \(n=1\), the only graph of that order has no edges and is the balanced complete bipartite graph specified above. Let \(n\ge2\), and first assume \(G\) is triangle-free with \(m=\lfloor n^2/4\rfloor\) edges. In particular \(m>0\), so choose an edge \(uv\). By the lemma, \(\deg(u)+\deg(v)=n\). The sets \(A=N(u)\) and \(B=N(v)\) are disjoint because \(G\) is triangle-free. Their sizes sum to \(n\), so they partition \(V(G)\). Each is independent: an edge between two vertices of \(N(u)\), for example, would form a triangle with \(u\); the same reasoning applies to \(N(v)\). Thus every edge of \(G\) goes between \(A\) and \(B\), and \(m\le |A||B|\).

For nonnegative integers \(a=|A|\), \(b=|B|\) with \(a+b=n\), the identity \(4ab=(a+b)^2-(a-b)^2\) gives \(ab\le\lfloor n^2/4\rfloor\). Hence \(\lfloor n^2/4\rfloor=m\le |A||B|\le\lfloor n^2/4\rfloor\). All these quantities are equal. Equality in the product bound forces the part sizes to differ by at most one, so \(A,B\) have sizes \(\lfloor n/2\rfloor,\lceil n/2\rceil\). Since \(G\) has \(|A||B|\) edges and there are exactly \(|A||B|\) possible edges between the parts, every such edge is present. Therefore \(G\) is balanced and complete bipartite.

Conversely, a complete bipartite graph has no triangle, since each edge goes between its two independent parts. If those parts are balanced on \(n\) vertices, its edge count is \(\lfloor n/2\rfloor\lceil n/2\rceil=\lfloor n^2/4\rfloor\). This proves both directions. \(\square\)

Worked Equality Cases

Common Pitfall and Why the Equality Conditions Matter

A common mistake is to say that equality in the odd-order case follows directly from equality in the real-valued bound \(m\le n^2/4\). For \(n=5\), however, the extremal integer edge count is \(6\), while \(n^2/4=25/4=6.25\). Thus \(m=6\) does not make \(m=n^2/4\). The correction is to use the integer degree sequence: at equality, the degree sum is \(12\), and the minimum possible square sum for five integer degrees summing to \(12\) is \(2\cdot3^2+3\cdot2^2=30\). The edge inequality gives an upper bound \(mn=6\cdot5=30\), so the square sum is exactly \(30\) and every edge has endpoint-degree sum \(5\).

The neighborhood argument then turns this numerical condition into structure. For an edge \(uv\), triangle-freeness makes \(N(u)\) and \(N(v)\) disjoint; equality makes their sizes sum to all \(n\) vertices. They form independent parts, and the edge count can reach the Mantel bound only when the parts are as balanced as possible and every cross-edge is present. This explains why the equality case is rigid: an unbalanced complete bipartite graph can still be triangle-free, but it has too few possible cross-edges.