Переберите все вершины, разделите их по степеням.
Если все имеют одинаковую степень, это возможно только при наличии вершины, имеющей степень n - 1.
Если вы можете разделить их на 2 различных набора степеней: давайте назовем X набором с более низкой степенью и Y - с более высокой. Давайте назовем dg (X) и dg (Y) степень этих вершин
- Если у одного из разделов есть только 1 вершина и ее степень равна 0 или количество вершин в другом наборе, удалите его
- Если dg (Y) - dg (X)> 1, это невозможно
- Если dg (Y) - dg (X) = 1 и | Y | = dg (X), проверьте, связана ли вершина из X со всеми вершинами из Y, и удалите ее.
- Если dg (Y) - dg (X) = 1 и | X | = dg (Y), проверьте, связана ли вершина из Y со всеми вершинами из X, и удалите ее.
- Любой другой случай невозможен с 2 разделами
Если вы можете разделить на 3 набора:
- Одна из них должна иметь только 1 вершину, и эта вершина должна быть соединена со всеми вершинами из другого набора наивысших степеней и ни с одним из оставшихся наборов. Разница в степени между другим набором наивысшей степени и оставшимся набором также должна составлять 1
Любой другой случай, это невозможно