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...