Showing graphs with more than $\lfloor\frac{n^2}{4}\rfloor$ edges have a $3$-cycle.

Question

From "A Brief Introduction to Spectral Graph Theory" Exercise 1.2 states

A graph on $n$ vertices that contains no 3-cycles has at most $\lfloor \frac{n^2}{4}\rfloor$ edges.

My thought process was to suppose otherwise. Then by the Handshaking Lemma:

$$\sum_{v \in V} \deg(v) = 2|E| > 2\left\lfloor\frac{n^2}{4}\right\rfloor = \frac{n^2}{2}$$

Furthermore, as there are $n$ vertices: $$\frac{\sum_{v \in V} \deg(v)}{n} > \frac{n}{2}$$

Thus, the average degree is $> n/2$. From here I am stuck. I thought an avenue of approach would be to consider a vertex $v$ with maximal degree. $v$ must be connected to over half of the vertices. Furthermore, none of its neighbors can be connected (otherwise there would be a $3$-cycle) but I am not exactly sure how to continue this line of reasoning. Any hints would be appreciated.

Answer 1

Though I agree with Misha Lavrov that this is a deceivingly placed exercise, you can come up with a proof using ideas you have outlined, together with an application of the AM-GM inequality: for non-negative reals $x$ and $y$, $\sqrt{xy}\leq \frac{x+y}{2}$.

Let $G$ be a graph with no $3$-cycle. We show $G$ has at most $\lfloor\frac{n^2}{4}\rfloor$ edges. As you have observed, no two neighbours of a vertex are adjacent, i.e., the neighbourhood of any vertex is an independent set. Moreover, the size of a largest independent set is thus an upper bound on the degree of a vertex in $G$. Let $I$ be a largest independent set in $G$, and let $J=V(G)\backslash I$. By the handshaking lemma

$$ 2|E(G)|=\sum_{v\in V(G)}\deg(v) = \sum_{v\in I}\deg(v)+\sum_{v\in J}\deg(v). $$

Now, every edge with one end in $I$ has its other end in $J$. Thus

$$ \sum_{v\in I}\deg(v)\leq \sum_{v\in J}\deg(v) , $$ so $$ |E(G)|\leq \sum_{v\in J}\deg(v) \leq |J||I|, $$ where we use the previously established bound $d(v)\leq |I|$. Finally, using the AM-GM inequality,

$$ |J||I|\leq \frac{(|J|+|I|)^2}{4} = \frac{n^2}{4}, $$ so $|E(G)|\leq \frac{n^2}{4}$, and since the number of edges of a graph is an integer, $|E(G)|\leq \lfloor\frac{n^2}{4}\rfloor$, as desired.

Answer 2

Here is another way to do it using a specialization of the Cauchy-Schwarz inequality. The inequality we will need is $$\sum_{i=1}^n u_i^2 \geq \frac{1}{n}\left(\sum_{i=1}^n u_i \right)^2.$$ Now, let $G$ be a graph on $n$ vertices containing no 3-cycles. Consider the set $S = \{(x,y,z): x\sim y,x \sim z\}$. Let's count this set in two different ways. First, for a single vertex $x \in V(G)$, the number of pairs of vertices $(y,z)$ that are adjacent to $x$ will be $d(x)^2$. Thus, $$|S| = \sum_{x\in V(G)}d(x)^2 \geq \frac{1}{n}\left(\sum_{x \in V(G)} d(x)\right)^2 = \frac{(2|E(G)|)^2}{n}.$$ Here we used the inequality mentioned above and the handshaking lemma. Next, for a singe pair of adjacent vertices $x \sim y$, the number of vertices $z$ that are adjacent to $x$ is $d(x)$ since $G$ has no 3-cycles. Thus, $$|S| = \sum_{x \sim y}d(x) = \sum_{xy \in E(G)} (d(x) + d(y)) \leq n|E(G)|.$$ Putting these together, we have $\frac{(2|E(G)|^2)}{n} \leq n|E(G)|$ and rearranging yields $|E(G)|\leq \frac{n^2}{4}$. And since the number of edges in a graph is always an integer, $|E(G)| \leq \lfloor \frac{n^2}{4}\rfloor$.