TIFR CSE 2021 | Part A | Question: 6

Question

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$ $\textit{vertices}$ in which there is a subset $M$ of $m$ $\textit{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 the matching $M$ with both end points in the set $B$?

• A. $p^{2}$
• B. $1-\left ( 1-p^{2} \right )^{m}$
• C. $p^{2m}$
• D. $\left ( 1-p^{2} \right )^{m}$
• E. $1-\left ( 1-p\left ( 1-p \right ) \right )^{m}$

Answer 1

$\text{Probability(selecting any vertex)} = p~,$

$\text{Probability(getting any particular edge)} =  p^2, $

$\text{Probability(not getting any particular edge)} = (1-p^2)$,

$\text{as there are total} \textit{ m edges}  \text{ in the Matching set} \textit{ M,}$

$\text{Probability(not getting any of these} \textit{ m edges}) = (1-p^2)^m$,

$\text{Probability(getting at-least 1 edge from M)}\\ \> = \text{1 – Probability(not getting any edge from M)} \\ \> = 1 – (1-p^2)^m$

Option B.

Comments

Are we takling this question in this way like we are only concerning about the edges in the matching only about the vertices in B. Because by (1-p^2)^m meant we talking about the edges not present in matching.