1. The prover generates an isomorphic graph to a given graph $H$ wherein he knows the Hamiltonian cycles of $G$ and hence for $H$ too. Multiple rounds of questioning either the isomorphism from $G$ to $H$ or hamiltonian cycle in $H$ ensures that the probability of fooling decreases exponentially.
  2. The prover provides the coloring for nodes on a particular edge asked by the verifier. For a valid coloring any such edge must be also valid hence ensuring that the prover cannot fool the verifier.
  3. \[\sum_{i=1}^{n}\left(\frac12\right)^{2i}=\frac 14\frac{1-(1/2)^{2n}}{1-(1/2)^2}\sim \frac 13\]
  4. \[\sum_{i=1}^{n}\left(\frac12\right)^{3i}=\frac18\frac{1-(1/2)^{3n}}{1-(1/2)^3}\sim\frac17\]
  5. That would be same as two valid english sentences with each letter having fixed distance between corresponding letters, but since language is quite complex that would be very small.
  6. That would mean that we would have a substitution that transforms one valid english sentence to another, still very small.
  7. No, not perfectly secure because messages that are obtained by decoding cipher text using different key characters at $i$ at $n/2+i$ can not be obtained since the key has such a property, hence it is not truly random because some plain texts have greater probability.
  8. Total messages reachable are $k!\frac nk=n(k-1)!<n!$