Peggy claims she can color this graph with three colors so that every edge joins two different colors. She wants to convince Victor of this without revealing anything about her coloring.
Convincing. If Peggy does not know a valid coloring, whatever she commits to has at least one edge with two equal colors. Victor picks that edge with probability at least 1/k, where k is the number of edges, and since Peggy committed before he chose, she cannot adapt. Over r independent rounds she gets away with probability at most (1 − 1/k)r, which shrinks exponentially.
Zero knowledge. In each round Victor sees two different colors on one edge. Because Peggy shuffled her colors with a fresh random permutation, that pair is uniformly random among all pairs of distinct colors. Victor could have produced such a transcript on his own, without Peggy, so he learns nothing beyond the fact that she passed.
The commitment. G is a one-way function: computing G(s) from s is easy, but going back from G(s) to s is practically impossible, and so is finding a second input with the same output. Publishing G(s) therefore locks Peggy in: to change a color later she would need a second string with the same hash. The random prefix is what keeps the color hidden. Without it, Victor could simply compute G(red), G(green) and G(blue) and compare.