A fun little formula from Graph Theory

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 .

Advertisement