Lesson 3

How can you convince your friends that you know a 3-coloring of a given large graph without revealing anything about the 3-coloring itself? You can proceed as follows. Draw this graph on the board. Then your friends leave the room, and you randomly shuffle the three colors, color each vertex, and cover it. Your friends return to the room, choose a random edge, and uncover the ends of that edge. If the colors of the two vertices are the same, your friends immediately understand that you had an incorrect coloring. If they are different, then either you have a correct coloring, or your friends chose a correctly colored edge in your incorrect coloring. If there is an incorrectly colored edge in your coloring, your friends will point to it with a probability of at least \(1/m\), where \(m\) is the number of edges. If you now repeat this experiment \(cm\) times, the probability that your coloring is incorrect and your friends do not notice will drop to \[\left(1-\frac{1}{m}\right)^{cm}< e^{-c}\ .\] It is important to note that on each iteration, you must reshuffle the colors in the 3-coloring—then your friends will indeed learn nothing about the coloring itself.