3-coloring graph zero-knowledge proof I was researching about zero-knowledge proofs and in this link http://web.mit.edu/~ezyang/Public/graph/svg.html I've seen the exercise question:


Currently, you can only select adjacent pairs of nodes to check. Would the proof still be zero knowledge if you could pick arbitrary pairs of nodes to check?


I think it would still be "zero knowledge" because it shouldn't leak information to verifier, but there won't be a proof if you select non-adjacent pairs since the reveal phase doesn't prove anything. Is this a trick question?
Yes, it would still be zero knowledge. However, it wouldn't be a proof of anything, since whether the colors matched or not, you still know nothing about whether the graph is actually 3-colored or not. It's not a trick question -- just a bad one.