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
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 .