TIFR CSE 2024 | Part B | Question: 14

Question

For an undirected graph $G$, let $\bar{G}$ refer to the complement (a graph on the same vertex set as $G$, with $(i, j)$ as an edge in $\bar{G}$ if and only if it is not an edge in $G$ ). Consider the following statements.

1. $G$ has a vertex-cover of size at most $k$.
2. $\bar{G}$ has an independent set of size at least $k$.
3. $G$ has an independent set of size at least $n-k$.
4. $G$ has a clique of size at least $k$.
5. $\bar{G}$ has a clique of size at least $n-k$.

Which of the following is true for any graph $G$ and its complement graph $\bar{G}$?

• A. (i) is equivalent to (iii) and (iv).
• B. (i) is equivalent to (iii) and (v).
• C. (i) is equivalent to (ii) and (iv).
• D. (i) is equivalent to (ii) and (v)
• E. None of the five statements are equivalent to each other.