The proof that the Independent-Set problem is NP-complete depends on a construction which reduces 3SAT to Independent Sets. Apply this construction to the 3SAT instance:

(u+v+w)(-v+-w+x)(-u+-x+y)(x+-y+z)(u+-w+-z)

Note that - denotes negation, e.g., -v stands for the literal NOT v. Also, remember that the construction involves the creation of nodes denoted [i,j]. The node [i,j] corresponds to the jth literal of the ith clause. For example, [1,2] corresponds to the occurrence of v.

After performing the construction, identify from the list below the one pair of nodes that does NOT have an edge between them.

a) [2,2] and [4,3]

b) [5,1] and [5,2]

c) [1,1] and [3,1]

d) [4,3] and [5,3]