Question 39: A graph is called a cluster graph if and only if it is a…

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph.

Determine, for each statement given, if it is true or false.

Based on the above data, answer the given subquestions.