These are always adjacent nodes being compared. Assuming the solution is correct, adjacent nodes will always have a different color. So the most information th

These are always adjacent nodes being compared. Assuming the solution is correct, adjacent nodes will always have a different color. So the most information that can leak is the correctness of the solution. Which is exactly what we need.