# A fun little formula from Graph Theory

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

Let ${G=(V,E)}$ be a graph, where we view ${E}$ as a set of ${2}$-element subsets of ${V}$. For ${v\in V}$, denote by ${d(v)}$ the degree of ${v}$. (Notation and terminology as in my graph theory lecture notes.)

Lemma 1. ${\sum_{uv\in E}d(u)+d(v) = \sum_{u\in V}d(u)^{2}}$.

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 ${f:V\longrightarrow\mathbb{N}}$ be any function. Then

$\displaystyle \sum_{uv\in E}f(u)+f(v)=\sum_{v\in V}d(u)f(u).$

Proof: Given ${v}$, the term ${f(v)}$ appears on the right hand side once for each edge of which ${v}$ is an endpoint. $\Box$

Lemma 1 follows by taking ${f=d}$.

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

Theorem 3 (Mantel’s Theorem). Suppose that ${G}$ is triangle-free, of order ${n}$, and of size ${e}$. Then

$\displaystyle e\leq\Big\lfloor\frac{n^{2}}{4}\Big\rfloor.$

Proof: Since ${G}$ is triangle-free, for every ${uv\in E}$ we have ${N(u)\cap N(v)=\emptyset}$. Therefore ${d(u)+d(v)\leq n}$. Summing across edges and using Lemma 1, we have

$\displaystyle \begin{array}{rclr} \sum_{v\in V}d(v)^{2}=\sum_{uv\in E}d(u)+d(v) &\leq& ne. \end{array}$

Combining these things, we have

$\displaystyle \begin{array}{rclr} 4e^{2} &=& \big(\sum_{v\in V}d(v)\big)^{2} &\text{by the degree formula}\\\\ &\leq& n\sum_{v\in V}d(v)^{2} &\text{by Cauchy--Schwarz}\\\\ &\leq& n^{2}e, \end{array}$

as required. $\Box$

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 ${K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}}$ is triangle-free and has size ${\lfloor\frac{n^{2}}{4}\rfloor}$.

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

Proposition 4. Let ${G}$ be triangle-free, of order ${n}$, and of size ${e(G)=\lfloor\frac{n^{2}}{4}\rfloor}$. Then ${G}$ is isomorphic to ${K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}}$.

Proof: If ${e(G)=\lfloor\frac{n^{2}}{4}\rfloor}$, then each inequality in the above proof of Mantel’s Theorem must be an equality. In particular, for each ${uv\in E}$ we have ${d(u)+d(v)=n}$. Thus the neighbourhoods of ${u}$ and of ${v}$ form a partition of the vertex set of ${G}$. It follows that ${G}$ is complete bipartite, and up to isomorphism the only such graph to have size ${\lfloor\frac{n^{2}}{4}\rfloor}$ is ${K_{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil}}$. $\Box$