<p>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.</p>

CC BY-SA 3.0
2017-06-22T16:54:39.690Z
2017-06-22T16:54:39.690Z
David
<p>I was researching about zero-knowledge proofs and in this link <a href="http://web.mit.edu/~ezyang/Public/graph/svg.html" rel="nofollow noreferrer">http://web.mit.edu/~ezyang/Public/graph/svg.html</a> I've seen the exercise question:</p>

<ul>
<li>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?</li>
</ul>

<p>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?</p>

CC BY-SA 3.0
2017-09-29T19:20:32.497Z
You are correct.
vy32
<graph-colouring><zero-knowledge>
3-coloring graph zero-knowledge proof
EralpB
# 3-coloring graph zero-knowledge proof

(Asked by: username_0 on 2017-06-22)

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?

**Tags:** graph-colouring, zero-knowledge
> **Comments:**
> **username_1**: You are correct.  

---

## 1 answers

### Answer by username_2 on 2017-06-22. Score: 3 | Accepted answer

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.


---

