Now if "C" = {"S""i" : "i" ∈ "D"} is a feasible solution of the set cover problem for some subset "D" ⊆ "I", then "D" is a dominating set for "G", with |"D"| = |"C"|: First, for each "u" ∈ "U" there is an "i" ∈ "D" such that "u" ∈ "S""i", and by construction, "u" and "i" are adjacent in "G"; hence "u" is dominated by "i". Second, since "D" must be nonempty, each "i" ∈ "I" is adjacent to a vertex in "D".