How do I prove that the clique problem is polynomial-time reducible to the odd cycle transversal problem?

Question

I have the following problem:

Let $H=(W, F)$ a graph and $k \in \mathbb{N^*}$ be an instance for problem $\textbf{CMP}$ (i.e. the clique problem). Let $W'$ a set of new vertices, $|W'|=|H|=n$. We define the following graph, $G=(V, E)$: $V=W \cup W'$, $E=\{xy | x, y \in V, xy \not\in F$ and $|W' \cap \{x, y\}| \leq 1\}$. Show that $H$ contains a clique of cardinality at least $k$ if and only if $G$ contains a subset of vertices $U$, $|U| \leq p=n-k$, such that $G-U$ is bipartite.

I understand that I have to prove the clique problem is polynomially reducible to the odd cycle transversal problem in order to solve this, but that's all I've got. My professor said this was actually very easy to prove, and I feel like that's true and I'm missing something obvious, but I can't quite figure out how these two problems are connected. I thought I could assume that $G$ contains odd-length cycles and go from there, but according to the definition above, $G$ is already a bipartite graph, which means I can't do that so now I'm completely out of ideas.

Answer 1

Though your definition of $E$ is not clear. I am assuming that $E = \{(x,y) \mid x \in W \textrm{ and } y \in W'\} \, \cup \{(x,y) \mid x,y \in W \textrm{ and } (x,y) \notin F\}$. In other words, $E$ contain all edges between sets $W$ and $W'$, and the edges that are not in $F$.

Proof Forward Direction: Suppose $H$ contains a clique of size at most $k$. Let the vertices of this clique be the set $C_W \subseteq W$. It is easy to see for the graph $G$, the set $W \setminus C_W$ is an odd cycle traversal of $G$. And, the set $W \setminus C_W$ has size $n-k$. This proves the forward direction.

Proof Reverse Direction: Suppose $G$ has an odd cycle traversal $V_O$ of size at least $n-k$. Let us define its left side as $V_L = W \cup V_O$ and its right side as $V_R = W' \cup V_O$. Let $G'$ be the bipartite graph obtained by removing $V_O$ from $G$.

Now, note the following observations:

1. Any vertex from $V_L$ and any vertex from $V_R$ can not be in the same partite set of $G'$

2. All vertices of $V_R$ must be in the same partite set of $G'$.

Therefore, the graph $G'$ must contain the partite sets as: $V_L$ and $V_R$. It means, there is no edge within $V_L$. Since $|V_L| \geq k$. Therefore, in the original graph $H$, the set $V_L$ forms a clique of size at least $k$. This completes the proof of the reverse direction.