Extra material : Day 9

Theorem (Mantel 1907) Let G be a simple graph on n vertices. If G contains more than ⌊\frac{n^{2}}{4} ⌋ edges, then G contains a triangle.

Remark : If n = 2k is even then the complete bipartite graph K_{k,k} has n vertices, n^{2}/4 edges and no triangles. If n = 2k +1 is odd then the complete bipartite graph K_{k,k+1} has n vertices, ⌊n^{2}/4⌋ edges and no triangles. So Mantel’s Theorem is the best-possible result.

Proof of Theorem : We assign to each vertex v of G a non-negative real number q_{v} such that

∑_{v∈V} q_{v} = 1.

We refer to q_{v} as the ‘charge’ on the vertex v. We’ll be interested in how to distribute the charge so as to maximise the quantity

S := ∑_{{v,w}∈E(G)} q_{v}q_{w}.

Let x, y be any two non-adjacent vertices in G. Let X (resp. Y) denote the total charge on the vertices adjacent to x (resp. y). WLOG, suppose X ≥ Y. Suppose we move all the charge on y to x. Then the change in S is given by

ΔS = (X − Y)q_{y} ≥ 0.

It follows that S attains a maximum when all the charge is concentrated on a complete subgraph of G. Now if G contains no triangles, then the only complete subgraphs in G consist of a single edge. So S is maximised when we have charges q and 1 − q on two adjacent vertices, for some q ∈ [0, 1]. Then

S = S(q) = q(1 − q).

This one-variable function attains its’ maximum at q = 1/2 and so the maximum of S is 1/4.

Suppose we were instead to distribute the charge uniformly over all n vertices. Then each vertex gets charge 1/n and so in this case

S = \frac{1}{n^{2}} |E(G)|.

Hence, if G contains no triangles, it follows that

\frac{1}{n^{2}} |E(G)| ≤ 1/4

⇒ |E(G)| ≤ \frac{n^{2}}{4} ,

as required.