A.56 library(ugraphs): Graph manipulation library
AllApplicationManualNameSummaryHelp

Availability::- use_module(library(ugraphs)).(can be autoloaded)
Sourcecomplement(+UGraphIn, -UGraphOut)
UGraphOut is a ugraph with an edge between all vertices that are not connected in UGraphIn and all edges from UGraphIn removed. Example: 
?- complement([1-[3,5],2-[4],3-[],
               4-[1,2,7,5],5-[],6-[],7-[],8-[]], NL).
NL = [1-[2,4,6,7,8],2-[1,3,5,6,7,8],3-[1,2,4,5,6,7,8],
      4-[3,5,6,8],5-[1,2,3,4,6,7,8],6-[1,2,3,4,5,7,8],
      7-[1,2,3,4,5,6,8],8-[1,2,3,4,5,6,7]]
To be done
Simple two-step algorithm. You could be smarter, I suppose.