Zero knowledge proof - case of graph 3-coloring (not understanding the concept)
Your misunderstanding stems from stating a wrong protocol for ZK 3-color verification. In fact the protocol is a bit more complex:
The prover first &quot;commits&quot; to colors. This means that he cannot change its commitment afterwards, but at the same time, he does not reveal the colors themselves.
Then, once the verifier asks for an edge, the prover &quot;opens&quot; its commitment, revealing the colors of that edge alone.
Since its commitment is binding, the prover cannot change the colors after committing to them. So if the prover does not have a legal coloring, he must commit to some invalid coloring of at least one edge, and will be found with some small probability.
This is repeated, each time with a new permutation of the colors, and new commitments.