gm learning

完全グラフの辺彩色にチャレンジ！

　完全グラフの頂点彩色は極めて簡単です．なぜなら，頂点をすべて違う色で塗ればよいからです．

　ところが，辺彩色となると，そう簡単ではありませんよ．下のアプレットを利用して，完全グラフの辺彩色にチャレンジしてください．

　頂点を必要なだけ作って， [クリーク化]ボタンをクリックすれば，完全グラフができあがります．さらに，[正多角形配置]ボタンをクリックすれば，形が整います．

　答えを述べておくと，頂点数が偶数ならば，その数より１だけ少ない色数で，完全グラフは辺彩色ができます．頂点数が奇数のときは，その数と同じ色数で可能です．

　頂点が少ないときには，答えどおりの辺彩色ができるでしょう．はたして，上で述べたような一般的な答えにつながる辺彩色の方法を，あなたは発見できるでしょうか？

　ヒントは正多角形配置をうまく利用することです！