# Probability of having a link in union of Erdos Renyi random graph

We have two Erdos-Renyi random graphs, $$G_1$$ and $$G_2$$, generated with probability $$p_1$$ and $$p_2$$, respectively. If we take the union $$G_1$$ $$\bigcup$$ $$G_2$$, we obtain another Erdos-Renyi graph, $$G_3$$.

I know that the probability of having a link in $$G_3$$ is: $$p_1 + p_2 - p_1p_2$$ but I cannot understand why.

• $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ – saulspatz Oct 12 '18 at 14:35

Approach 1: $$G_3$$ contains edge $$vw$$ if either $$G_1$$ or $$G_2$$ contains it. We add the probabilities of each of those cases, then subtract the overlap, getting \begin{align} \Pr[vw \in E(G_3)] &= \Pr[vw \in E(G_1)] + \Pr[vw \in E(G_2)] - \Pr[vw \in E(G_1) \cap E(G_2)] \\ &= p_1 + p_2 - p_1p_2. \end{align} It's crucial that $$G_1$$ and $$G_2$$ are independent, so we can just multiply $$p_1$$ and $$p_2$$ to find the probability that an edge is in both graphs.
Approach 2: $$G_3$$ contains an edge $$vw$$ unless neither $$G_1$$ nor $$G_2$$ contains it. So the probability that $$G_3$$ does not have the edge is $$\Pr[vw \notin E(G_3)] = \Pr[vw \notin E(G_1)] \cdot \Pr[vw \notin E(G_2)] = (1-p_1)(1-p_2)$$ and therefore the probability $$G_3$$ does have the edge is $$\Pr[vw \in E(G_3)] = 1 - (1-p_1)(1-p_2) = p_1 + p_2 - p_1 p_2.$$