This note is aimed at those taking my fourth-year Graph Theory course.

Let be a graph, where we view as a set of -element subsets of . For , denote by the degree of . (Notation and terminology as in my graph theory lecture notes.)

Lemma 1..

It’s easy to let this little formula go by without much thought. It gets used in the proof of Mantel’s Theorem. But I want to bring it to the fore, as an example of a simple but perhaps opaque statement, which becomes clearer with a little abstraction.

Consider the following stronger statement.

Lemma 2.Let be any function. Then

*Proof:* Given , the term appears on the right hand side once for each edge of which is an endpoint.

Lemma 1 follows by taking .

Let’s see how Lemma 1 is used in a proof of Mantel’s Theorem.

Theorem 3 (Mantel’s Theorem).Suppose that is triangle-free, of order , and of size . Then

*Proof: * Since is triangle-free, for every we have . Therefore . Summing across edges and using Lemma 1, we have

Combining these things, we have

as required.

So there we have it. Lemma 1 has a straightforward application in this proof of Mantel’s Theorem.

Note also that the complete bipartite graph is triangle-free and has size .

Often bundled into the statement of Mantel’s Theorem is the additional claim:

Proposition 4.Let be triangle-free, of order , and of size . Then is isomorphic to .

*Proof:* If , then each inequality in the above proof of Mantel’s Theorem must be an equality. In particular, for each we have . Thus the neighbourhoods of and of form a partition of the vertex set of . It follows that is complete bipartite, and up to isomorphism the only such graph to have size is .