離散数学 オイラーグラフ、ハミルトングラフの質問です。

質問

離散数学　オイラーグラフ、ハミルトングラフの質問です。

添付データの画像のグラフについて考えています。
括弧の中に書いてあることが正しいのかと、このグラフはハミルトングラフであるか？
また、その理由を教えてください。

このグラフは位数（５）の（完全）グラフであり（４）次の（４-正則）グラフ

３辺形は（5Ｃ3＝　１０個）
４辺形は（5C4 * 2 = 10個)

（すべての辺から偶数個の辺が出ているためオイラーグラフ）

回答No.1

R_Earl · ベストアンサー

> （すべての辺から偶数個の辺が出ているためオイラーグラフ）

オイラーグラフの条件は

全ての「頂点」から偶数個の辺が出ている

ではないでしょうか。

> このグラフはハミルトングラフであるか？
> また、その理由を教えてください。

ハミルトン閉路が存在すれば、
それだけで「ハミルトングラフである」と言えるはずですよね。
なので総当たりでもなんでも良いので、
とにかく1個ハミルトン閉路を見つけましょう。

今回のグラフの場合、
グラフをなぞってみるとすぐにハミルトン閉路が見つかります。

お礼

> （すべての辺から偶数個の辺が出ているためオイラーグラフ）
書き間違えていました。ご指摘ありがとうございます。

ハミルトングラフはよく分かっておらずＮＰ困難関係のものかと思い苦しんでいたので目からうろこの思いです。

試験問題の範囲なのですがおかげさまで助かりました。

素早い回答ありがとうございました。