Вот тут есть демонстрация этого алгоритма со стороны проверяющего:
http://web.mit.edu/~ezyang/Public/graph/svg.html
Там предлагают выбрать граф — и в одном из случаев к нам пришёл человек с честной раскраской, а в другом нас пытаются обмануть. Confidence внизу отвечает за оценку на "1 минус вероятность того, что обманщику столько раундов подряд бы везло".