Hacker News new | ask | show | jobs
by Donwangugi 4140 days ago
An isomorphism between two graphs indicates that bijection exists between two graphs, or that there exists a method to permute one graph's vertices so that they are equal to another one.

What Merlin is saying to Arthur is that no matter what kind of graph K Arthur comes up with, it cannot be congruent to both G and H, or, that there exists no method to create a graph that is both G and H.

Lastly it is zero-knowledge because Arthur learns nothing of the relation between G and H, only that the K he computes is not both of them simultaneously.

Not sure if that helps.