A Degree-Sum Proof of Mantel's Theorem

The Degree-Sum Idea

Mantel’s theorem bounds the number of edges in a triangle-free graph. The degree-sum proof uses a local fact about each edge: its endpoints cannot have a common neighbor, since that neighbor would complete a triangle. Consequently, the two endpoint neighborhoods fit disjointly inside the vertex set. Summing this restriction over the edges turns a local observation into a global edge bound.

Throughout, graphs are finite and simple. The degree \(\deg(v)\) is the number of vertices adjacent to \(v\), and \(N(v)\) is the set of those neighbors. A triangle is a cycle of length \(3\); a graph is triangle-free if it contains no triangle. Write \(n=|V(G)|\) and \(m=|E(G)|\).

Proof. The neighborhoods \(N(u)\) and \(N(v)\) are disjoint. Indeed, if a vertex \(w\) belonged to both, then \(uw\), \(vw\), and \(uv\) would be the three edges of a triangle. Since both neighborhoods are subsets of \(V(G)\), disjointness gives \[ \deg(u)+\deg(v)=|N(u)|+|N(v)|=|N(u)\cup N(v)|\le n. \] This proves the claim for each edge. \(\square\)

The bound is summed over edges. In that sum, a vertex \(v\) contributes its degree once for each edge incident with it. Since it has \(\deg(v)\) such edges, its total contribution is \(\deg(v)^2\). Thus the sum of the endpoint-degree sums over all edges is the sum of squared degrees.

This identity can also be checked by counting the same contributions in the opposite order: first choose an edge and add the degrees of its endpoints, or first choose a vertex \(v\) and add \(\deg(v)\) once for each of its \(\deg(v)\) incident edges.

Mantel’s Bound

Proof. If \(n=0\), the graph has no vertices and hence no edges, so \(m=0=\lfloor n^2/4\rfloor\). Now suppose \(n>0\). If \(m=0\), the claimed inequality holds because \(0\le\lfloor n^2/4\rfloor\). It remains to consider \(m>0\).

Apply the lemma to each of the \(m\) edges and sum. Using the double-counting identity gives \[ \sum_{v\in V(G)}\deg(v)^2 =\sum_{uv\in E(G)}\bigl(\deg(u)+\deg(v)\bigr) \le mn. \] Each edge contributes \(1\) to the degree of each of its two endpoints, so \(\sum_v\deg(v)=2m\). For any \(n\) real numbers \(x_v\), their squared deviations from their mean have nonnegative sum: \[ 0\le\sum_{v\in V(G)}\left(x_v-\frac{\sum_w x_w}{n}\right)^2 =\sum_{v\in V(G)}x_v^2-\frac{\left(\sum_v x_v\right)^2}{n}. \] Taking \(x_v=\deg(v)\) therefore yields \[ \sum_{v\in V(G)}\deg(v)^2 \ge \frac{\left(\sum_v\deg(v)\right)^2}{n} =\frac{4m^2}{n}. \] Combining the upper and lower bounds gives \(4m^2/n\le mn\). Since \(m>0\) and \(n>0\), division by \(m\) and multiplication by \(n/4\) give \(m\le n^2/4\). Because \(m\) is an integer, \(m\le\lfloor n^2/4\rfloor\), as required. \(\square\)

The proof has two distinct ingredients. Triangle-freeness supplies the edge-by-edge bound \(\deg(u)+\deg(v)\le n\). The sum-of-squares inequality then says that a fixed total degree cannot have an arbitrarily small sum of squared degrees. Together, these force an upper bound on the number of edges.

Worked Applications of the Degree Sum

Common Pitfalls

Using \(n-1\) instead of \(n\). A tempting but incorrect claim is that the two endpoint neighborhoods together contain at most \(n-1\) vertices. They need only be disjoint subsets of the \(n\)-vertex set; they can cover all \(n\) vertices. In the first example, every edge has endpoint-degree sum \(3+2=5=n\), so a bound of \(n-1=4\) would already be false. The correct conclusion is \(\deg(u)+\deg(v)\le n\), not \(\le n-1\).

Counting endpoint contributions only once per vertex. The sum over edges is not generally \(\sum_v\deg(v)\). A vertex \(v\) appears on \(\deg(v)\) incident edges, contributing \(\deg(v)\) each time, for a total of \(\deg(v)^2\). For the first example, the edge-endpoint sum is \(30\), whereas the ordinary degree sum is \(12\); the squared-degree sum is \(30\), as the identity requires.

Dividing when there are no edges. The proof divides by \(m\) only in the case \(m>0\). If \(m=0\), the desired edge bound holds directly. Likewise, the sum-of-squares argument divides by \(n\), so the empty graph must be handled separately. Keeping these cases explicit makes the argument valid for every finite simple triangle-free graph.

The degree-sum method is useful because it converts local restrictions into a global estimate through a transparent double count. Here, forbidden triangles limit the degrees at each edge, while the total degree records the edge count. The same style of reasoning is a central tool in extremal graph theory, where the aim is to bound the size of a graph under a structural prohibition.