Return to Revisions

Let's color each edge red with probability $p$, independently of other edges. Two vertices of $G$ glue together if and only if they are connected with a red path. Hence, your $V(G')$ is exactly the number of connected components of the subgraph, obtained from $G$ by keeping the red edges and removing all other (non-colored) edges. That is, you are interested in the expected number of connected components in the random subgraph of $G$, obtained by deleting every edge of $G$, randomly and independently from other edges, with probability $q:=1-p$. This quantity has been studied: see, for instance, this paper by Alon, or just Google for something like "connected components of a random subgraph".