Inequality regarding simple graphs with no $4$-cycles I've been recently reading on Graph Theory, which is one of those areas I always felt lazy to approach when I trained for mathematical Olympiads. As it turns out, this is one of the fields that do show up later on really frecuently :(
Anyhow, I was reading the article
Firke, F. A., Kosek, P. M., Nash, E. D., & Williford, J. (2013). Extremal graphs without 4-cycles. Journal of Combinatorial Theory, Series B, 103(3), 327-336.
on bounds regarding graphs without $4$-cycles — as the title suggests — and had some questions on one of its earlier statements.

Lemma 1. Let $q$ be a natural number greater than $2$ and let $G$ be a $C_4$-free graph on $q^2 + q$ vertices with at least $E_0$ edges. Then the maximum degree of a vertex in $G$ is at most $q + 2$.
Proof. Let $v$ be a vertex of $G$ of maximum degree $d$, and suppose that $d \geqslant q + 3$. Let $e$ be the number of edges of $G , e \geqslant \frac12 q(q + 1)^2 − q$. We proceed by bounding the number of $2$-paths in $G$ which have no endpoints in $\Gamma (v)$ [where $\Gamma(v)$ represents the set of vertices in the neighborhood of $v$]. This gives us: $$\binom{n-d}{2}\geqslant \sum _{v\neq u}\binom{d(v)-1}{2}$$ [where, I believe, $n$ represents the number of vertices in $G$.]

Question 1. What's the meaning of »$2$-paths«? And, what are the authors counting in the inequality? $\binom{n-d}{2}$ stands for the number of possible connections between two vertices of the set $G\setminus \Gamma (v) $, right? But, what does $\sum _{v\neq u}\binom{d(v)-1}{2}$ represent? Shouldn't it be $\sum _{u\neq v}\binom{d(u)-1}{2}$? From what they derive through Jensen, I would say that they are considering the degrees of elements in $G\setminus \{v\}$, but still don't understand what they are counting...
Later on, in the proof of the Lemma 1, the authors introduce some inequalities which I am struggling to follow, since they are stated without proof:

However, we also have: $$\begin{align*}(q + &1)(2e − 2n − d + 2) − (n − 1)(n − d − 1)\\ &\geqslant (q^2 −2)d−q^3 −2q^2 +q+1\\
&\geqslant (q^2 −2)(q+3)−q^3 −3q^2 +1\geqslant q^2 −q−5\end{align*}$$
(...)
We also have the inequality: $$\begin{align*}(2e−n−d+1)−(q+1)(n−d)&\geqslant −q^2 −3q+1+qd\\& \geqslant −q^2 −3q+1+q(q+3)=1>0\end{align*}$$

Could you please give a hint regarding the proof of these inequalities?
Thanks in advance!
 A: Q1: this proof is more than a little cryptic. I think I finally understand what's going on. I will prove the inequality $\binom{n - d}{2} \geq \sum_{u \neq v} \binom{d(u) - 1}{2}$ in more detail. (You were right — the authors mixed up $u$ and $v$.)

A. Notation. All graphs are simple. Given a graph $G$ and a vertex $v \in V(G)$, we let $\Gamma(v) \subseteq V(G)$ denote the set of neighbours of $v$. Note: since $G$ is simple, we have $v \notin \Gamma(v)$.
B. Lemma. Let $G$ be a $C_4$-free graph, and let $u,v \in V(G)$ be distinct. Then $|\Gamma(u) \cap \Gamma(v)| \leq 1$.
Proof. Suppose that $\Gamma(u) \cap \Gamma(v)$ contains two distinct vertices $x$ and $y$. Then $G$ contains a $4$-cycle $uxvyu$, contrary to our assumption. $\quad\Box$
C. Definition. For an integer $k \geq 0$, let $P_k$ denote the path of length $k$ (i.e. the path on $k + 1$ vertices). If $G$ is a graph, then a $k$-path in $G$ is a subgraph of $G$ which is isomorphic to $P_k$. (In particular, a $2$-path is given by a pair of distinct, adjacent edges.)
D. Lemma. Let $G$ be a $C_4$-free graph, and let $S \subseteq V(G)$ be a vertex set. Then the number of $2$-paths with both endpoints in $S$ is at most $\binom{|S|}{2}$.
Proof. By definition, every $2$-path has two different endpoints. For every possible pair of endpoints $\{u,v\}$ in $S$, there can be at most one $2$-path whose endpoints are $u$ and $v$, for otherwise $u$ and $v$ would have multiple common neighbours, contradicting Lemma B. Therefore the total number of $2$-paths with both endpoints in $S$ is at most $\binom{|S|}{2}$. $\quad\Box$
E. Lemma. Let $G$ be a $C_4$-free graph, let $S \subseteq V(G)$ be a vertex set, and let $u \in V(G)$ be a vertex. Then the number of $2$-paths in $G$ having both endpoints in $S$ and having middle vertex $u$ is exactly $\binom{|\Gamma(u) \cap S|}{2}$.
Proof. Choosing such a $2$-path is equivalent to choosing two distinct edges in $E(u,S)$, the set of edges with one endpoint equal to $u$ and the other endpoint an element of $S$. Since $G$ is simple, we have $|E(u,S)| = |\Gamma(u) \cap S|$, and the result follows. $\quad\Box$
Proof of the inequality. Let $\beta$ be the number of $2$-paths with both endpoints in $V(G) \setminus \Gamma(v)$. By Lemma D, we have $\beta \leq \binom{n - d}{2}$. Furthermore, by Lemma E we have $\beta = \sum_{u \in V(G)} \binom{|\Gamma(u) \setminus \Gamma(v)|}{2}$. For $u = v$, the contribution to this sum is $0$. For $u \neq v$, it follows from Lemma B that
$$ |\Gamma(u) \setminus \Gamma(v)| = |\Gamma(u)| - |\Gamma(u) \cap \Gamma(v)| \geq |\Gamma(u)| - 1 = d(u) - 1. $$
Therefore,
$$ \binom{n - d}{2} \geq \beta = \sum_{u \in V(G) \setminus \{v\}} \binom{|\Gamma(u) \setminus \Gamma(v)|}{2} \geq \sum_{u \in V(G) \setminus \{v\}} \binom{d(u) - 1}{2}. \tag*{$\Box$} $$

Q2: I think there is a misprint, and the first inequality should read
\begin{align*}
(q& + 1)(2e - 2n - d + 2) - (n - 1)(n - d - 1) \\
&\geq (q^2 - 2)d - q^3 - 2q^2 + q + 1\\
&\geq (q^2 - 2)(q + 3) - q^3 - 2q^2 + q + 1 \tag*{(this line is different)} \\
&= q^2 - q - 5.
\end{align*}
The difference is that the authors mistakenly replace $-2q^2 + q$ by $-3q^2$.
This inequality can be derived using the following steps:

*

*start with $(q + 1)(2e - 2n - d + 2) - (n - 1)(n - d - 1)$;

*substitute $n = q^2 + q$ and $e \geq \frac{1}{2}q(q + 1)^2 - q$ to obtain $(q^2 - 2)d - q^3 - 2q^2 + q + 1$;

*substitute $d \geq q + 3$ (and use that $q^2 - 2 > 0$) to obtain $(q^2 - 2)(q + 3) - q^3 - 2q^2 + q + 1$;

*simplify to obtain $q^2 - q - 5$.

The second inequality seems fine, and can be derived using the following steps:

*

*start with $(2e - n - d + 1) - (q + 1)(n - d)$;

*substitute $n = q^2 + q$ and $e \geq \frac{1}{2}q(q + 1)^2 - q$ to obtain $-q^2 - 3q + 1 + qd$;

*substitute $d \geq q + 3$ (and use that $q > 0$) to obtain $-q^2 - 3q + 1 + q(q + 3)$;

*simplify to obtain $1$.

