$\newcommand{\lln}{\operatorname{\lln}}\newcommand{\bb}{\binom}$We are going to deduce from \eqref{1} a bound better than the ultimate bound in \eqref{2}. Actually, we are going to obtain the exact asymptotic of the upper bound in \eqref{1}.
(In particular, it follows that the ultimate bound in \eqref{2} is not optimal. Already for this reason, it seems hard, if at all possible, to reconstruct the logic of Erdős and Rényi that allowed them to get \eqref{2} from \eqref{1}.)
To begin our consideration, note that the upper bound on $P$ in \eqref{1} is \begin{equation*} p_n:=\sum_{s=2}^{\ln\ln n}\bb ns \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r}, \end{equation*} where \begin{equation*} f_{s,r}:=\frac{\dbinom{\bb{n-s}2}{N_c-r}} {\dbinom{\bb n2} {N_c}}. \end{equation*}
Note that \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3}, \end{equation*} where \begin{equation*} \begin{aligned} P_1&:=N_c\cdots(N_c-r+1), \\ P_2&:=\Big(\bb n2-N_c\Big)\cdots\Big(\bb{n-s}2-N_c+r+1\Big), \\ P_3&:=\bb n2\cdots\Big(\bb{n-s}2+1\Big). \end{aligned} \end{equation*} Here and in what follows, $s$ is an integer in the interval $[2,\ln\ln n]$ and $r$ is an integer in the interval $[1,\bb s2]$.
To determine the asymptotics of $P_1,P_2,P_3$, we are going to use the following simple lemma, which will be proved at the end of this answer.
Lemma 1: If $a$ and $b$ are positive integers varying so that $b^3=o(a^2)$, then \begin{equation*} (a+b-1)\cdots a\sim\Big(a+\frac{b-1}2\Big)^b. \end{equation*}
Using Lemma 1 and letting \begin{equation*} q_{n,s}:=\bb n2-\bb{n-s}2=s(n-(s+1)/2), \end{equation*} uniformly in $s,r$ as specified above we get the following (as $n\to\infty$): \begin{equation*} P_1\sim\Big(N_c-\frac{r-1}2\Big)^r =N_c^r\Big(1-\frac{r-1}{2N_c}\Big)^r\sim N_c^r, \end{equation*} \begin{equation*} P_3\sim\Big(\bb n2-\frac{q_{n,s}-1}2\Big)^{q_{n,s}} =\bb n2^{q_{n,s}}\Big(1-\frac{q_{n,s}-1}{n(n-1)}\Big)^{q_{n,s}} \\ \sim \bb n2^{q_{n,s}} e^{-s^2}, \end{equation*} \begin{equation*} \begin{aligned} P_2&\sim\Big(\bb n2-N_c-\frac{q_{n,s}-r-1}2\Big)^{q_{n,s}-r} \\ &=\bb n2^{q_{n,s}-r}\Big(1-\frac{2N_c+q_{n,s}-r-1}{n(n-1)}\Big)^{q_{n,s}-r} \\ &\sim \bb n2^{q_{n,s}-r} e^{-s\ln n-2cs-s^2}. \end{aligned} \end{equation*} So, \begin{equation*} f_{s,r}=\frac{P_1 P_2}{P_3} \sim\rho_n^r e^{-2cs}n^{-s}, \end{equation*} where \begin{equation*} \rho_n:=\frac{N_c}{\bb n2}. \end{equation*} So, \begin{equation*} \sum_{r=1}^{\bb s2} \bb{\bb s2}r f_{s,r} =\Big((1+\rho_n)^{\bb s2}-1\Big)e^{-2cs}n^{-s}\sim\rho_n\bb s2 e^{-2cs}n^{-s} \\ \sim\bb s2\frac{\ln n}n\,e^{-2cs}n^{-s}. \end{equation*} So, \begin{equation*} \begin{aligned} p_n&\sim\frac{\ln n}n\,\sum_{s=2}^{\ln\ln n}\bb ns \bb s2 e^{-2cs}n^{-s} \\ &\le\frac{\ln n}n\,\sum_{s=2}^\infty\frac1{s!} \bb s2 e^{-2cs} \\ &=C\frac{\ln n}{n}, \end{aligned} \end{equation*} where $C:=\frac{1}{2} e^{e^{-2 c}-4 c}$.
Moreover, by dominated convergence, \begin{equation*} p_n\sim C\frac{\ln n}{n}. \quad\Box \end{equation*}
It remains to present
Proof of Lemma 1: \begin{equation*} \begin{aligned} \big((a+b-1)\cdots a\big)^2&=\prod_{j=0}^{b-1}(a+j)(a+b-1-j) \\ &=\prod_{j=0}^{b-1}\Big[\Big(a+\frac{b-1}2\Big)^2-\Big(\frac{b-1}2-j\Big)^2\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-\frac{(b-1-2j)^2}{(2a+b-1)^2}\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \prod_{j=0}^{b-1}\Big[1-O\Big(\frac{b^2}{a^2}\Big)\Big] \\ &=\Big(a+\frac{b-1}2\Big)^{2b} \Big[1-O\Big(\frac{b^3}{a^2}\Big)\Big] \\ &\sim \Big(a+\frac{b-1}2\Big)^{2b}. \quad\Box \end{aligned} \end{equation*}