Question 1

Figure from the passage in the original paper Based on the above data, answer the given subquestions. Consider the following graph. A triangle-free subset of seven vertices is highlighted. Find the size of the largest triangle-free subset of vertices in this graph. Example graph G (Figure 1) with grey and white vertices and some edges drawn bold Figure from the passage in the original paper Based on the above data, answer the given subquestions. The TRIANGLE-FREEDOM problem is the following: the input is a simple undirected graph *G* and a positive integer *k*. An instance (*G*, *k*) is a YES-instance if and only if *G* has a subset *S* of at least *k* vertices that are triangle-free.\ What can you say about TRIANGLE-FREEDOM? Check all that apply. Figure from the original question paper