Since the literals in a given clause are connected in the triangle, it is obvious that you cannot construct an independent set by picking two vertices from one triangle. But what would it mean in terms of the 3SAT problem if you did? For example if you picked x2 and x3 in the first triangle, then does this mean that x2 and x3 cannot both be true as this would not lead to a satisfying assignment?
If more than one literal in a clause is true in a satisfying assignment, we can still translate this into an independent set by arbitrarily picking one of the true literals in the clause and including the corresponding vertex in our independent set (but not the other two vertices in the same triangle even if the corresponding literals may be true as well).
You are genuinely awesome.
Since the literals in a given clause are connected in the triangle, it is obvious that you cannot construct an independent set by picking two vertices from one triangle. But what would it mean in terms of the 3SAT problem if you did? For example if you picked x2 and x3 in the first triangle, then does this mean that x2 and x3 cannot both be true as this would not lead to a satisfying assignment?
If more than one literal in a clause is true in a satisfying assignment, we can still translate this into an independent set by arbitrarily picking one of the true literals in the clause and including the corresponding vertex in our independent set (but not the other two vertices in the same triangle even if the corresponding literals may be true as well).
Thank you !!!!!
Thanks!