締切済み

ハミルトングラフの証明

2014/01/14 18:09

単純グラフGにn(>3)個の点があり隣接していない点v、wについてd(v)+d(w)>=nであるとする。このときGの隣接していない点s,tについて、GがハミルトングラフならGに辺stを追加したグラフG'もハミルトングラフである。これを証明せよという問題なのですが、考えてみるとこれは自明なのではないかと思います。しかし、証明問題なので自明の一言で片付けるわけにもいかず困っています。なにかうまい証明方法があればお教えください。回答、よろしくお願いします。