問題のグラフを \(G\) とします。\(G\) のある三角形に含まれる辺を辺とする \(G\) の部分グラフを \(H\) とします。

以下、「連結成分」といえば \(H\) に関するものをいいます。

• 回転は連結成分ごとの偶置換である

ことが分かります。これは実は必要十分な特徴づけになっていて、

• 連結成分ごとの偶置換は、回転の繰り返しにより実現できる

ことも示すことができます。\(n\) 点の連結成分上、好きな \(n-2\) 点を好きな位置にうつせることを帰納法により示すのが簡単でしょうか？

三角形の列挙がボトルネックとなり、例えば\(O(NM)\) 時間で解けます。なお、三角形の列挙を \(O(M\sqrt{M})\) 時間で行うアルゴリズムも存在します。