For an undirected graph $G$, let $\overline{G}$ refer to the complement (a graph on the same vertex set as $G$, with $(i, j)$ as an edge in $\overline{G}$ if and only if it is not an edge in $G$ ). Consider the following statements.
- $G$ has a vertex-cover of size at most $k$.
- $\overline{G}$ has an independent set of size at least $k$.
- $G$ has an independent set of size at least $n-k$.
- $G$ has a clique of size at least $k$.
- $\overline{G}$ has a clique of size at least $n-k$.
Which of the following is true for any graph $G$ and its complement graph $\overline{G}$?
- (i) is equivalent to (iii) and (iv).
- (i) is equivalent to (iii) and (v).
- (i) is equivalent to (ii) and (iv).
- (i) is equivalent to (ii) and (v)
