7 views
A matching in a graph is a set of edges such that no two edges in the set share a common vertex. Let $G$ be a graph on $n$ vertices in which there is a subset $M$ of $m$ edges which is a matching. Consider a random process where each vertex in the graph is independently selected with probability $0 < p < 1$ and let $B$ be the set of vertices so obtained. What is the probability that there exists at least one edge from matching $M$ with both end points in the set B?

(A) $p^2$

(B) $1 – (1 – p^2)^m$

(C) $p^{2m}$

(D) $(1 – p^2)^m$

(E) $1 – (1 – p(1 – p))^m$
| 7 views