I need a source where I can find a proof of Reiman's theorem:
If the graph G is quadrilateral($C_4$)-free, then
$$|E(G)| \leq \frac{|V(G)|}{4}(1 + \sqrt{4\cdot|V(G)| - 3})$$
Here is the idea of the proof:
Consider the set of ordered triplets
$$F= \{(u, v, w) : uv \in E(G), uw \in E(G)\}$$
$$|F| = \sum_{u \in V(G)}(d_G(u)(d_G(u) - 1))$$
On the other hand, as $G$ doesn't have $C_4$, then (can someone explain this inequality?)
$$|F| \leq n(n - 1)$$ where $n = |V(G)|.$
This part is already clear to me:
Each triplet is defined by its $2$ ends $u$ and $w$, you can choose these $2$ vertices in $\binom{n}{2}$ ways. These triplets are ordered, so we are getting the maximum capacitance of $F$ is $2\binom{n}{2}$. And, therefore, the above inequality holds.
Then, using Cauchy–Schwarz Inequality
we're getting full proof of the theorem.
Thanks in advance.
The key is to determine, for each ordered pair of vertices $v$, $w \in V(G)$, how many vertices $u \in V(G)$ are such that $(u, v, w) \in F$.
Our assumption that $G$ is $C_4$-free means that for every ordered pair $v$, $w \in V(G)$, there exists at most one vertex $u$ such that $uv$, $uw \in E(G)$. This is because if there existed distinct $v$, $w$, $u$, $u' \in V(G)$ such that $uv$, $uw$, $u'v$, $u'w \in E(G)$, then $u$, $u'$, $v$, and $w$ would form a copy of $C_4$, a contradiction.
It follows that $|F|$ is at most the number of ordered pairs of vertices of $G$. That is, $$|F| \leq 2\binom{n}{2} = n(n - 1),$$ as we wanted to show.