In the example, the vertices colors for a graph edge are requested, but how can one trust that those colors aren't being generated on-the-fly? Effectively, how can I trust that the "warehouse" isn't cheating me?
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")
http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing
Encrypt the answer and maybe some salt or if you're really brave, some known plaintext provided by the other guy (here be dragons), give the pub key for every node to everyone, split the private key using SSSS or some other strategy, and give all SSSS key-halve to the other guy and google only gives up precisely two of their halves upon request so you only get to SSSS reassemble the private keys for two nodes and thus only know two nodes.
There are some other schemes involving hashing that I feel a little fuzzier about.
Also look into "double spend" algos for digital cash. Go ahead, opfor, make my day, you double spend a token and you get more data but GOOG gets the transaction's swiss bank account number so the financial transaction auto-completes. That might take a little more fooling around at the protocol level to set up.
Similarly in the equivalent digital experiences, the prover commits to a value and must be able to prove that it didn't change it (for instance it must provide the verifier a hash of the chosen color + some random salt).