15パズル

http://d.hatena.ne.jp/noripy/20051219/1135013638
15 Puzzle - Marginal Leaves

宿題ねー、とか言っている間にmarginさんも書いていて、しかも論文までリンクされてしまいました。というわけで、イメージしていた証明のアイデアだけ書いておきます。えーと、marginさんが参照している論文はよく見ていないので、証明が似ているのかさえわかりません(爆)。
盤面上に市松模様を書いておきます。すると、一回パズルを動かすたびに、空白部分は白と黒の色の上に交互に乗っかります。また、一回動かすごとに、偶置換と奇置換も入れ替わります。というわけで、その二つの排他的論理和(というよりもxorと書いたほうがわかりやすいか)をとれば、それは強互換に対する不変量になります。というわけで、強同値類の数は最低二つ。
二つ以上にならないことは帰納法でやっつけます。n=m=2から始めます。このときに強同値類がまさに二つある、っていうのは簡単でしょう。全ての とに対して(n',m')-強同値類がまさに二つあると仮定します。このとき(n+1, m)-強同値類が二つあることをいいたいわけですが、これは(n+1, m)の盤面を左端から(n, m)と右端から(2, m)に分けてうにうにやればできるはずです。
ってわけで、たとえば市松模様の白と白の部分をどこか一組でもつなげてやってしまうと、強同値類はひとつになります。
…間違っていたら教えてください…

問題は、これを一般グラフに拡大した場合ですが。ものすごく単純なケースとして、グラフが単にn個の頂点が一直線に並んでいるようなものなら、強互換にできることは単に空白を動かしていくことだけなので、(n-1)!個になるのではないかと。n個の頂点からなるループを考えると、(n-2)!個だろうと。
この二つの単純なケースを(本質的に)除いた場合、強同値類の個数として取りうる自然数はどのようなものがあるのかな、というのが面白いかなと思うのですが。たとえば、強同値類が3個になるようなグラフとかあるんかな、と。
こうなると、正直私にはどう考え始めていいやらわからないんですが。誰か考えてみませんか？(他力本願)