1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.