How do zero knowledge protocol with vertex-3-coloring work? I'm currently not sure if I understood how the zero knowledge protocol with vertex-3-coloring works. I'll describe what I think I've understood and I'll write my questions in bold.

Zero-knowledge-protocols in general

What are they good for? What is a typical scenario?

I think they are good for authentication (The verifier wants to authenticate the prover):


The prover sends a graph for which he knows know a three-coloring to the verifier. They have to be sure that an attacker can't change this graph before the verifier gets it.
When the verifier wants to authenticate the prover, she asks for the colors of the vertices of one edge:


The prover chooses a permutation for colors
The prover applies this permutation the his coloring
The prover sends the permutated colors of the two vertices of one edge to the verifier

The verifier repeats step 2 as often as she wants.


I've found a good interactive example where you can play this game.
This site includeas another question:

[...] but also raises the question whether or not the prover is just outright cheating


How can I be sure that the prover actually has a three-coloring? 

e.g. lets assume that the prover always answers (red, blue) for any request of the verifier. What would go wrong?

(After reading this great example I think there has to be some probability-part that I currently miss)

Vertex 3-coloring

How can the prover efficiently generate a big graph with a valid three coloring? How can he make sure that it is actually difficult to get a three coloring for this graph?
Zero knowledge in general


  What are they good for? What is a typical scenario?


This is an interesting question. One application is authentication: You can choose the secret yourself and not even the server will know it, and it will never be transmitted in any way. You just prove you know the secret again and again. However, in practice this is rarely used. Another application is.... security theory. If a protocol can be shown to hold some zero knowledge property, you are sure the correct protocol execution will not reveal any information about the secrets. 

Vertex 3-coloring


  How can I be sure that the prover actually has a three-coloring?


You mixed up two essential steps in your description: The color permutation is chosen and applied FIRST, and then the verifier chooses the edge. And therefore, the prover has to send the entire graph with commitments of the colors to the verifier first (or he could still be cheating).


  How can he make sure that it is actually difficult to get a three coloring for this graph?


He can make sure that it's difficult to find a coloring if the graph is huge. It's an NP problem, so it can be solved in exponential time. But if the parameter $n$ is small, then $x^n$ is still manageable.


  How can the prover efficiently generate a big graph with a valid three coloring? 


You should not use the word "efficient" with this problem/proof at all. That is not possible. The main problem is that the probability of detecting cheating is $1/e$, where $e$ is the number of edges.Therefore, with $n$ rounds the probability of successful cheating is $(\frac{e-1}{e})^n$. It does go towards 0, but VERY slowly in a big graph. A common goal for error in cryptography is around $(\frac{1}{2})^{80}$, which would imply an incredibly huge amount of rounds.

About generating a 3-colored graph: Start with 1 node and then add random nodes and edges in a way, which doesn't break the 3 coloring. This should take $O(n)$ time.