I'am currently working my way through the proof of Erdős, Kleitman and Rothschild on the Asymptotic Enumeration of $K_n$-free Graphs (see https://users.renyi.hu/~p_erdos/1976-03.pdf). In particular I am struggling with the first part of the proof of lemma 8 on page 26 of that reference:
We are given a triangle free Graph on $n$ vertices and want to show that there cannot be a $C_5$. We know that in our construction every vertex is connected to some set $Q$ that is adjacent to some set $R$ with size $\frac{n}{2} \pm \frac{n^{5/8}}{2}$. I will denote this as $R_v$ of a given vertex $v\in V$. We also know that for two adjacent vertices $v,w$ we have $$|(V\setminus R_v)\cap(V\setminus R_w)|\leq \frac{n}{40}.$$ If we now assume that there is a $C_5$ with vertices ${v_1, \dots, v_5}$ the authors follow from the first fact that for two non adjacent vertices $$|(V\setminus R_{v_i})\cap(V\setminus R_{v_j})|\geq \frac{n}{2} - \frac{3n^{5/8}}{2} - \frac{n}{20}$$ holds. I figured you calculate it along something like this: \begin{align} |(V\setminus R_{v_i})\cap(V\setminus R_{v_j})| &= |V\setminus R_{v_i}|+|V\setminus R_{v_i}| - |(V\setminus R_{v_i})\cup(V\setminus R_{v_j})| \\ &\geq n - n^{5/8} - |V\setminus (R_{v_i}\cap R_{v_j})| \end{align} But here I am lost, as I am not quite sure on how to find a lower bound for $|R_{v_i}\cap R_{v_j}|$. I tried to work with the fact that for every vertex the set $Q$ has a size $\sqrt{n}$ and that the respective set $R$ has to avoid it as we would otherwise find a triangle in $G$, but everything got pretty messy. So I was wondering if anyone has a tip on how to see that the above inequality holds.
Best regards and many thanks in advance!