Suppose Prover has multiple (>1) valid solutions to the problem. What changes if the Prover not only picks representation at random, but also pick a solution at random each round?
To me it looks that at least in this case entirely different solution and different representations are permutations of the solution, therefore both are allowed?
Sure, it's allowed, and makes sense in this particular example. But someone reading this might think that the scheme depends on using a random coloring in the second round, which is precisely not the case.
In ZKP, usually the claim is "I have constructed this 3-colorable graph, and I wish to prove to you that it is 3-colorable without giving you any info about the coloring", and I only know the one colorability that I constructed the graph with (so the narrative given about Google calculating a coloring for you isn't the best analogy to begin with).
Or, "Here's a number that's a product of two big primes, a fact which I will prove to you without giving you a hint on what the primes are," in which there is obviously only one solution.
Nothing changes. If something did change, that could[1] mean that information about your solution was being leaked (since this means that different solutions behave differently under the ZKP process, which cannot be the case for it to be zero-knowledge).
ZKP is about proving you have a solution. If you have many, good for you.
To me it looks that at least in this case entirely different solution and different representations are permutations of the solution, therefore both are allowed?