Edge probability for connected Erdős–Rényi model Consider the Erdős–Rényi model $G_{n,p}$ with corresponding probability measure $\mathbb{P}_{n,p}$. For any two vertices $x,y$, $\mathbb{P}_{n,p}[E_{x,y}]=p$, where $E_{x,y}$ is the event that there exists an edge between $x$ and $y$.
I need to estimate (especially bound from above) the following probability for two fixed vertices $x,y$ and $G \in G_{n,p}$:
$\begin{equation} 
\mathbb{P}_{n,p}[E_{x,y}|G \text{ is connected}]
\end{equation}$
Supplement: $p=\frac{c}{n}$ for some constant $c >1$ (I forgot this in my first version).
 A: Let $E_{xy}$ be the event that $xy$ is an edge of $G$ and let $C$ be the event that $G$ is connected. By Bayes' Theorem, $$P(E_{xy} \mid C) = \frac{P(C \mid E_{xy})P(E_{xy})}{P(C)} = p\frac{P(C \mid E_{xy})}{P(C)}.$$ So the question amounts to estimating how much knowing that $G$ has an edge improves the probability of $G$ being connected.
The graph $G$ is connected precisely if it contains a spanning tree $T$. Furthermore, knowing that $xy$ is an edge of $G$, we may further require that $T$ contains the edge $xy$. So we have a crude upper bound $$P(C \mid E_{xy}) \leq \sum_{xy \in T} P(T \subseteq G \mid E_{xy}),$$ where $T$ ranges over all trees on the labeled vertex set $\{1,\ldots,n\}$. By Cayley's Formula, there are $n^{n-2}$ such $T$ and, since each such $T$ has exactly $n-1$ edges, there are $2n^{n-3}$ such trees that contain the edge $xy$. For each $T$ containing $xy$, $P(T \subseteq G \mid E_{xy}) = p^{n-2}$, so $$P(C \mid E_{xy}) \leq 2n^{n-3}p^{n-2},$$ or equivalently $$P(E_{xy} \mid C) \leq \frac{2n^{n-3}p^{n-1}}{P(C)}.$$ Clearly, this bound is only useful for small $p$. When $p$ is large, the trivial bound $$P(E_{xy} \mid C) \leq \frac{p}{P(C)}$$ is of greater use.
The classic paper
Gilbert, E.N., Random graphs, Ann. Math. Stat. 30, 1141-1144 (1959). ZBL0168.40801, contains exact formulas for $P(C)$. Gilbert's method can also be used to compute $Q_n = P(C \mid E_{xy})$ using the recurrence $$1-Q_n = \sum_{k=2}^{n-1} \binom{n-2}{k-2}Q_k(1-p)^{k(n-k)}.$$ (The $k$th term is the conditional probability that the connected component containing $x,y$ has exactly $k$ elements.) Thus
$Q_{2} = 1$
$Q_{3} = -p^2
 + 2 p$
$Q_{4} = -2 p^5
 + 9 p^4
 - 14 p^3
 + 8 p^2$
$Q_{5} = 6 p^9
 - 48 p^8
 + 162 p^7
 - 298 p^6
 + 318 p^5
 - 189 p^4
 + 50 p^3$
I haven't tried to prove it but it seems that the bound $2n^{n-3}p^{n-2}$ from above is exactly the leading term of $Q_n$. At least this is the case for $n \leq 60$ by direct calculation.
A: I agree strongly with Peter in the comments: if you're interested in $p \gg \frac{\log n}{n}$, then don't do any hard work, just show the answer is essentially $p$ since the graph is essentially always connected.
In particular, let $E$ be the event that the edge exists and $C$ the event that the graph is connected. By the law of total probability,
\begin{align*}
  P(E|C)P(C) + P(E,\lnot C) &= p
\end{align*}
so
\begin{align*}
  P(E|C) &= \frac{p - P(E,\lnot C)}{P(C)}  \\
         &\leq \frac{p}{1-o(1)}
\end{align*}
where a lot is known about bounds on the $o(1)$ (the probability the graph is disconnected).
(By the way, naturally, we immediately have $P(E|C) \geq p$. To prove it, $P(E|C) = p P(C|E)/P(C)$, and $P(C|E) \geq P(C)$ as guaranteed existence of $(x,y)$ can only raise the chance of connectedness.)
