The OP glosses over this a bit, but it's mentioned in the footnotes: the "hats" represent a commitment scheme, which is a way for the prover commit to a specifi

The OP glosses over this a bit, but it's mentioned in the footnotes: the "hats" represent a commitment scheme, which is a way for the prover commit to a specific color assignment, before revealing what that assignment actually is. When the verifying party chooses the two vertices he wants to see, the prover can reveal only those two, and the verifier actually has two things to check: 1) the colors revealed are actually two different colors (otherwise the purported solution obviously isn't correct) 2) the colors revealed are consistent with the prover's overall commitment. (in other words, that the prover didn't change his answer "on-the-fly")