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


Please leave a reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s