離散数学の問題が解けなくて困っています。

質問

ペテルセングラフはすべての頂点を一度ずつ通るサイクルを含まないことを示せ（ハミルトンサイクルという）

という課題なんですが、どのように示したらよいのかわかりません。背理法などをつかうのでしょうか？教えていただけたら幸いです。よろしくお願いします。

回答No.2

Tacosan · ベストアンサー

あ, あれれぇ?
図を描けば, 結構簡単に理解できるはずなんだけどなぁ....
違う表現でもう 1回流れを書くと,
・外の五角形の辺を全部使うことはできない (1周して戻ってしまうのでアウト).
・つまり, 使わない辺は少なくとも 1本存在する.
・但し, 「連続する 2本の辺を使わない」ことも不可能である (頂点の次数が足らなくなる).
・ということは, 外の五角形の辺で考えると対称性から
１．1本だけ使わない (残り 4本は使う)
２．連続しない 2本を使わない (残り 3本を使う)
の 2通りしか存在しない.
この時点で, どのような状況になっているかを図に描いてみてください. ハミルトン閉路が存在しないことは, わりと自明だと思います.

回答No.1

Tacosan

えっと, ペテルセングラフって「外が五角形, 中が五芒星で外と中の対応する頂点間に辺がやっぱり 1本ずつある」ってやつですよね?
ちょっと考えたんですけど, 「作ろうと努力しても不可能」ということを示せばいいんじゃないかな.
まず, 外の五角形の辺を全て使うわけにはいかないので, 使われない辺が少なくとも 1本は存在します. この辺を削除すると, 両端点の次数が 2 になるので自動的に経路が確定します.
さらに外の五角形の辺の使い方を考えるんですが, 対称性から「両方使う」と「一方だけ使う」の 2通りしかなく, 両方をチェックすればいいような気がします.
少なくとも, 脳内ではこれでいい感じ.

お礼

回答ありがとうございます。私の頭が足りないために理解できませんでした。しかし、参考にさせていただきます。ありがとうございました。