Prob #2
VerifyOpt1:=proc(n,G,B1,B2) local i,j:
for i from 1 to n do
 for j from i+1 to n do
     if (member({i,j},G) and B2[{B1[i],B1[j]}]=0) or 
        (not(member({i,j},G)) and B2[{B1[i],B1[j]}]=1) then
         RETURN(false):
     fi:
  od:
od:
RETURN(true):
end:


ZKP12:=proc(n,G,pi,Opt) local B1,B2,H,i,j,sig:
sig:=randperm(n):
for i from 1 to n do
 B1[i]:=sig[i]:
od:


for i from 1 to n do
 for j from i+1 to n do
   if member ({i,j},G) then
     B2[{sig[i],sig[j]}]:=1:
   else
    B2[{sig[i],sig[j]}]:=0:
   fi:
od:
od:


H:={seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]}:


if Opt=1 then
  VerifyOpt1(n,G,B1,B2):
else
  if H={1} then RETURN(true): fi:
fi:
end:


Test run
n:=7: p:=1/2: Gpi := RHG(n,p): G:=Gpi[1]; pi:=Gpi[2];
 G := {{1, 2}, {1, 4}, {2, 3}, {2, 5}, {2, 6}, {2, 7}, {3, 6},  {3, 7}, {4, 7}, {5, 6}, {5, 7}}
 pi := [5, 7, 4, 1, 2, 3, 6]


Opt:=1: ZKP12(n,G,pi,Opt);
                              true


Opt:=2: ZKP12(n,G,pi,Opt);
                              true


Prob #3
ZKP:=proc(n,G,pi,K) local i,Opt:
for i from 1 to K do
  if LD(1/2)=true then
    Opt:=1:
  else
    Opt:=2:
  fi:
  if ZKP12(n,G,pi,Opt) = false then 
    RETURN(false):
  fi: 
od:
RETURN(true):
End:


Test run
K:=100: ZKP(n,G,pi,K);
                              true