graph avoiding cycle of length 4

Question

let $G$ be a simple graph on $n$ vertices such that $G$ has no cycle of length $4$. show that $e(G)\le \frac{n}{4}(1+\sqrt{4n-3})$ where $e(G)$ denotes the number of the edges of the graph $G$.

Answer 1

I included a proof of what you want in a question of mine where I asked for a tighter bound if the graph avoids also cycles of length 3: (I use the convention $m:=e(G)$)

I try to show if $G$ has no subgraph $C_4$, then $m \leq \frac{n}{4}(1+\sqrt{4n-3})$. We can consider the amount $k$ of subgraphs of $G$ that look like $K_{1,2}$ (a "cherry"). Certainly if we (double) count those, considering a vertice in the center of the cherry, we get:

$$k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$

Now if we don't allow squares a pair of vertices $\{v,w\}$ can be endpoints of only one cherry, otherwise we would have a cycle, therefore

$$\binom{n}{2} \geq k=\sum_{v\in V}\binom{\text{deg}(v)}{2}$$

Then due to convexity of $\binom{x}{2}$ and the Jensen-Inequality one might conclude now that $m \leq \frac{1}{4} \cdot \left(\sqrt{n^2 (4n-3)}+n\right) $.

This is a link to Jensen's inequality in case you don't know it.

Edit: As the operator asked for more details:

Define $\varphi(x):=\binom{n}{2}$, it is easy to see that $\varphi$ is convex. Therefore we have that

$$\varphi\left(\frac{\sum x_i}{n}\right) \le \frac{\sum \varphi (x_i)}{n} \iff \sum \varphi (x_i) \geq n\cdot \varphi\left(\frac{\sum x_i}{n}\right)$$

And therefore

$$\binom{n}{2} \geq \sum_{v\in V}\binom{\text{deg}(v)}{2} \geq n\cdot \binom{\frac{1}{n}\sum_{v\in V}\text{deg}(v)}{2}=n\cdot\binom{\frac{2m}{n}}{2}$$

Because the sum over all degrees of the nodes corresponds to twice the amount of edges. Expanding the binomial on both sides yields your result.