Finding the largest triangle-free induced subgraph in a given simple graph $G$ is NP-Complete.

Question

Definition:

If $G=(V,E)$ is a simple graph, $H_G$ is a graph which has all of the vertices and edges of $G$, and also for each edge of $G$ like $e=(x,y)\space$, $H_G$ has a new vertex which is connected to both $x$ and $y$.

---

The induced subgraph $S$ of $G=(V,E)$ is called triangle-free, If for each $u,v,w\in V(S)$, at least one of the edges $uv, vw,uw$ are not in $E(G)$.

Our goal is to prove that the problem of finding the largest triangle-free induced subgraph in a given simple graph $G$ is NP-Complete.

---

Question:

a) Prove that for a given simple graph $G=(V,E)$, $H_G$ has a triangle-free induced subgraph with $|E|+k$ vertices, Iff $G$ has an independent set with $k$ vertices.

b) Conclude that the problem of of finding the largest triangle-free induced subgraph in a given simple graph $G$ is NP-Complete.

---

My try:

Assume that $G$ has an independent set of size $k$. It means that there are $k$ vertices in $G$ like $v_1,\dots,v_k$ such that there is no edges between them. But, How is this related to $H_G$ having a triangle-free induced subgraph with $|E|+k$ vertices? Maybe $k$ of the vertices are $v_1,\dots,v_k$ and the other $|E|$ vertices are the ones added to $G$ in the process of making $H_G$. But, this is just a guess... I can't prove that...

Answer 1

You are correct, and here's an argument. For an edge $e\in E(G)$ let $v^e$ denote the new vertex which we added to form $H_G$, that is, the new vertex which is connected to the endpoints of $e$. Assume that $v_1,\dots,v_k$ is an independent set in $G$. Then $\{v_1,\dots,v_k\}\cup\{v^e:e\in E(G)\}$ is triangle-free in $H_G$. Indeed, what would it mean if this set had a triangle? Well, there are no edges among the $v^e$'s, so in order to have a triangle, it must use two vertices from $\{v_1,\dots,v_k\}$; but this can't happen as this set is independent. Thus, the largest triangle-free induced subgraph of $H_G$ has size at least $\alpha(G)+|E(G)|$.

It remains to show the reverse inequality; namely if $H_G$ has a triangle-free induced subgraph on $|E(G)|+k$ vertices, then $\alpha(G)\geq k$. Let $S\subseteq V(H_G)$ have no triangle and $|S|\geq |E(G)|+k$. We can decompose $S$ into $S_1=S\cap V(G)$ and $S_2=S\cap\{v^e:e\in E(G)\}$. Notice that if $e\in E(S_1)$, then $v^e\notin S_2$, otherwise we have a triangle in $S$. In fact, without loss, we may suppose that $S_2=\{v^e:e\notin E(S_1)\}$ as this can only make $S$ larger and does not add any triangles. Thus, we have $|S|=|S_1|+|E(G)|-|E(S_1)|$. However, we assumed $|S|\geq |E(G)|+k$, so we must have $|S_1|-|E(S_1)|\geq k$. Now, what we can do is take $S_1$ and destroy any edge in $S_1$ by deleting one of its endpoints. After doing so, we are left with an independent set in $G$ of size at least $|S_1|-|E(S_1)|\geq k$, so $\alpha(G)\geq k$.