Три домика, три колодца и 12 миллионов графов

[wataru]

Проверка на графах размера 10 - это хорошо, конечно, но верность алгоритма не гарантирует. Алгоритм вполне может пропускать конструкции, невозможные на 10 вершинах.

[Delnor]

Согласен) полный перебор корректность не доказывает, в статье это оговорено прямо. Корректность самого алгоритма держится на доказательстве в статье Бойера и Мирволд, а перебор (у меня он проходил и на 11 вершинах, это миллиард с лишним графов) ловит ошибки реализации во всех маленьких конфигурациях.

Для больших графов у библиотеки есть другая страховка: ответ можно проверить его сертификатом, и тестовые прогоны делают это для каждого графа. Если ответ "планарен", укладку сверяют с исходным графом и формулой Эйлера. Если "непланарен", проверяют, что предъявленный подграф есть в исходном графе и это действительно растянутый K3,3 или K5. Неверный ответ на любом графе, где такая проверка включена, она поймает, сколько бы в нём ни было вершин. Остаётся ошибка на графе, который никто не прогонял, и тут вы правы