Well, in the protocol described in the OP, the verifier can't build an internal copy of the graph-coloring, because knowing that two adjacent vertices in the graph are two different colors doesn't help anything; that much is required of any solution. In the protocol I describe, the verifier can do that, because revealing more than two vertices simultaneously leaks information that isn't necessarily true of all possible solutions (at least, it can; if three vertices which connect in a triangle turn out to be three different colors, you haven't learned anything because any valid solution will have that property).
The problem I'm having is that I agree that the one-edge protocol is zero-knowledge (and that a verifier could be tricked indefinitely by a prover with a time machine), and obviously the two-edge protocol isn't zero-knowledge (and, in probably-related-but-I'm-not-sure news), a verifier using the two-edge protocol cannot be tricked indefinitely by a time machine). I can tell that, but I tell it by looking within my soul and thinking "yes, there is no information leak when one edge is revealed, but there is a leak when two edges are revealed". That's not a reliable method; I'd like to know how to prove that information does not leak through a protocol, and I don't see that anywhere in the OP.
Roughly speaking, the question here is: can you simulate a multi-edge protocol. That is, can you achieve the following properties using rewinding:
1. The 'fake Prover' simulating the protocol has no knowledge of an actual graph coloring.
2. From the Verifier's PoV, the distribution of the simulated (rewinding-based & fake) protocol transcript is identical to that of a real protocol run where the Prover really does a solution.
3. The simulation still requires only time polynomial in the problem instance (when you include all the rewinding trips).
I think if you follow this through you'll find that simulating a multi-edge protocol that 'looks like' a real transcript is highly challenging.
The reason for condition (3) is to rule out an obvious hack wherein the simulation takes so long that the 'fake Prover' can simply find solve the problem (e.g., by finding a graph coloring in an exponential number of time steps).
etc. etc, then simulating a two-edge protocol is, while more time-consuming than simulating a one-edge protocol, still pretty easy. If the record looks like
Trial 1: PASS (v1 red -- v2 green, v3 green -- v4 blue)
Trial 2: PASS (v1 blue -- v2 red, v7 blue -- v9 red)
Trial 3: PASS (v1 green -- v2 red, v7 green -- v4 red)
then after Trial 3 you can tell that the prover is cheating. The fake trials seem to achieve your properties (1) and (3). I guess they violate #2? What is the "distribution" of a simulated transcript?
Sorry my reply wasn't clear, I understood the question you were asking in your original comment. I was actually referring to your 2-edge protocol when I wrote that it seems the Verifier could not be tricked even in the simulated protocol (since it could detect inconsistencies as you mentioned).
I think the theorem says that if your Solver can successfully trick the Verifier in the simulated protocol (aka using the rewinding trick), then your protocol is zero-knowledge. But I'm really not sure... Let me know if you find a more satisfying answer.
The problem I'm having is that I agree that the one-edge protocol is zero-knowledge (and that a verifier could be tricked indefinitely by a prover with a time machine), and obviously the two-edge protocol isn't zero-knowledge (and, in probably-related-but-I'm-not-sure news), a verifier using the two-edge protocol cannot be tricked indefinitely by a time machine). I can tell that, but I tell it by looking within my soul and thinking "yes, there is no information leak when one edge is revealed, but there is a leak when two edges are revealed". That's not a reliable method; I'd like to know how to prove that information does not leak through a protocol, and I don't see that anywhere in the OP.