Алгоритм для независимого множества.

Question

Я работаю над своей домашней работой, и есть один вопрос, который я не могу понять. Нам дан следующий алгоритм:

On input ⟨G, k⟩, where G is a graph:
   Let vi be the vertex of minimum degree (if there are more than one 
   choice for vi, break ties by choosing the vertex with the smallest 
   label)
   Set S = {vi}
   Let N = {u ∈ V \ S | (u, v) ∈/ E for all v ∈ S} be the set of 
   vertices outside S that are not adjacent to any vertex in S
   While N is not empty
       Let vi be the vertex in N of minimum degree (breaking ties by 
       choosing the smallest label)
       Update S = S ∪ {vi}
       Update N = {u ∈ V \ S | (u, v) ∈/ E for all v ∈ S} to be the 
       set of vertices outside S that are not adjacent to any vertex 
       in S 
   End While
   accept if and only if |S| >= k.

Как видите, это простой алгоритм поиска независимого набора определенной длины в графе. Тем не менее, мы должны:

• Покажите, что возможно, что H отвергает ⟨G, k⟩, хотя ⟨G, k⟩ ∈ IS. Приведите такой пример ⟨G, k⟩, где граф G содержит не более 5 вершин.

Я пытался выработать решение в грубой форме, и, честно говоря, эта проблема кажется мне нелогичной. Я думал о граничных случаях, и все же кажется, что нет такого случая, когда размер S был бы меньше k, и в то же время ⟨G, k⟩ было бы ∈ IS.

PS Я не прошу решения, но если бы вы могли дать подсказку и подтолкнуть меня в правильном направлении, я был бы признателен!