A Curious Bound on the Complexity of Graphs With No 4-Cycles

Posted on November 5, 2021January 15, 2022 by Russell Schwartz

I encountered this rather bizarre looking fact in my undergraduate graph theory class:

Let $G$ be a connected graph with $n$ vertices and $m$ edges. If $G$ does not contain a $4$ -cycle, then $m \le \frac{n}{4}\left(1 + \sqrt{4n - 3}\right)$ .

This struck me as odd. For an unrestricted graph, the number of edges can be as large as $O\left(n^2\right)$ (e.g. the complete graph). This fact implies that the complexity drops to $O\left(n^{3/2}\right)$ if we simply stipulate that there are no cycles of length $4$ .

Let’s dive into a proof. We begin by defining some special subsets of $V$ :

$D_k = \{\{u, v\} \mid d(u, v) = k\} \subset 2^V$

Where $d(u, v)$ represents the distance (i.e. length of shortest path) from $u$ to $v$ . For example, $D_1$ gives all pairs of adjacent vertices and $D_2$ gives all pairs of (non-adjacent) vertices that have a mutual friend. Since the $D_k$ ‘s partition the set of all pairs of vertices, we have

$\binom{n}{2} = \sum_{k \in \mathbb{N}} |D_k|$

Now, let $v \in V$ and consider the quantity $\binom{\deg v}{2}$ , which counts the pairs of vertices in the neighborhood of $v$ . Either the vertices in these pairs are of distance 1 (if they are adjacent) or they are of distance 2 (since they are both adjacent to $v$ ). Observe that they cannot both be in the neighborhood of any other vertex – otherwise this would form a 4-cycle. Thus, summing over $v$ we count each pair of vertices exactly once:

$\sum_{v \in V} \binom{\deg v}{2} = |D_1| + |D_2|$

We now have:

(1) $\begin{align*} \binom{n}{2} \ge |D_1| + |D_2| &\ge \sum_{v \in V} \binom{\deg v}{2} \\ \frac{n(n-1)}{2} &\ge \sum_{v \in V} \frac{\deg v(\deg v - 1)}{2} \\ n(n-1) &\ge \sum_{v \in V} \deg^2 v - \sum_{v \in V} \deg v \\ n(n - 1) + 2m &\ge \sum_{v \in V} \deg^2 v \end{align*}$

Here we made use of the so-called handshake lemma, which states $\sum_{v \in V} \deg v = 2m$ .

Applying the Cauchy-Schwarz inequality:

$\begin{align*} \left(\sum_{v \in V} \deg v\right)^2 &\le \sum_{v \in V} \deg^2 v \sum_{v \in V} 1^2 = n\sum_{v \in V} \deg^2 v \end{align*}$

combining with (1):

$\begin{align*} (2m)^2 &\le n(n(n - 1) + 2m) \\ 4m^2 &\le n^2(n - 1) + 2mn \\ 4m^2 - 2mn &\le n^2(n - 1) % 16m^2 - 8mn + n^2 &\le 4n^3 - 3n^2 \\ % \left(\frac{4m}{n} - 1\right)^2 &\le 4n - 3 \\ % m &\le \frac{n}{4}\left(1 + \sqrt{4n - 3}\right) \end{align*}$

we get a quadratic in $m$ which we solve directly to get the desired result:

$\begin{align*} 16m^2 - 8mn + n^2 &\le 4n^3 - 3n^2 \\ \left(\frac{4m}{n} - 1\right)^2 &\le 4n - 3 \\ m &\le \frac{n}{4}\left(1 + \sqrt{4n - 3}\right) \end{align*}$

There is a neat construction (due, I think originally, to Erdös) for a family of graphs that achieve this asymptotic upper bound, showing that it is in fact a tight bound. For any prime number $p$ , we construct a graph of order $n = p^2$ by taking our vertices to be

$V = \mathbb{Z}_p \times \mathbb{Z}_p = \{(a, b) \mid a, b \in \mathbb{Z}_p\}$

Here, $\mathbb{Z}_p$ is the finite field of order $p$ . Our edge relation is given by

$(a, b) \sim (c, d) \iff ac = b + d$

Recall that all arithmetic in this field is done $\pmod p$ . It is easy to see that every vertex in the resulting graph will have degree $p$ . Thus, $m \ge np/2 = \Theta\left(p^3\right) = \Theta\left(n^{3/2}\right)$ . We do not necessarily have equality here since there may be self-adjacent vertices. If we decide to exclude these loops for the sake of the construction, the asymptotic complexity does not change.

It remains to show that we have not created any 4-cycles. Indeed, for any two vertices $(a, b)$ and $(c, d)$ , their neighborhoods have at most 1 vertex in common. This follows from the fact that the system