ハミルトングラフの証明

単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。
このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加した
グラフG'もハミルトングラフである。

これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。
しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。
なにかうまい証明方法があればお教えください。
回答、よろしくお願いします。

No.1 回答者： stomachman 回答日時： 2014/01/16 02:19

グラフG'がハミルトングラフの定義を満たす、ということを逐一確認すればいいんです。

自明なら容易でしょ？