The part not shown well here is that before your choice, you would receive a "commitment" for each vertex color in the graph for each iteration. The commitment allows the prover to provide a coloring that can't be changed after the round starts, but also where only the values for the chosen edge will have their commitment "opened".

If each round gets you an edge with different colors for each vertex, you can be confident it was able to 3-color the graph. You have the commitments, so the prover can't change the colors based on your requested edge, so if they didn't color it correctly you know there's some probability of getting one of the edge(s) where it had to give both vertices the same color. You can never be 100% sure it didn't lie and then get lucky each round, but you can do enough rounds to reach whatever probability of that makes you satisfied that it's honest.

What form could such a commitment take over the wire?

There's a bunch of committment schemes: https://en.wikipedia.org/wiki/Commitment_scheme , but a simple (although I'm not sure it's ideal) one would be to hash a random value concatenated with the message, transmit the hash as your commitment to that message, and to reveal it send the random value and message so the verifier can confirm the hash comes out the same.

But would your example commitment work in this case when the verifier never receives the "message" of the graph that's being committed to?

The "message" would have to be each vertex's color, separately, rather than the entire graph's coloring at once. Then when the verifier requests the edge for this round, the prover reveals those the commitments for the two vertices on that edge and only those two.

Since the prover doesn't know which edge will be selected and has to commit one color to each vertex, inspecting one random edge per round is enough. They either committed to a 3-coloring and any edge is valid, or they didn't and there's at least one edge we could pick to reject them. The rest of the graph doesn't need to be revealed for us to either gain confidence that they have a coloring or know for certain they do not.

Interesting! Thanks especially for the link to the Wikipedia page.

So in the demo, the black (uncolored) shape _kind of_ represents the commitment. Although as you pointed out, it doesn't explain how it is verified! Instead of a black shape, it would be a shape made out of hash values that are meaningless until the random number for any one of them is revealed. And the protocol is to only reveal one of them each time?

Exactly, the only difference is that two commitments would be revealed, since each vertex color is committed, if we let them commit to edges instead it would be much easier to lie!

I think you need a way for the prover to commit to the colors of every vertex before you choose which edge you want revealed.

Yeah, that's exactly what you need to keep it more honest. This demo doesn't really show that part of the protocol.

This demonstration is utter nonsense, because it's musing a critical step. By the automorphism of color permutations, all possible non-trivial reaponses are equivalent and prove nothing. What's missing is that the prover has to send you something like a salted hash of every edge coloring (called a "cryptographic commitment") in advance, so that you can verify that the revealed coloring matches what was already committed.

But since the number of distinct single edge colorings is tiny (6), you could crack the hash easily, so you need a fancier commitment protocol than just a hash, perhaps some sort of mutually trusted hashing oracle that only lets you send one query per proof.

Why do you need something fancier? Couldn't you commit to n=1..6 by hashing a k*n where k is a random integer?