質問<991>2002/10/22
奇点の数が奇数個の連結なグラフって存在するのでしょうか? もし存在するのであればその例を、 しないのであればその証明を教えてください。
お返事2002/10/27
from=武田
一筆書きは、必ず奇数点から奇数点へ向かうのが鉄則だから 途中は偶数点となる。 問題の奇数点が奇数個あるかだが、奇数点は始めと終わりの2個だけなので、奇数点が奇数個ある一筆書きは存在できない。 あとは全部偶数点でないと一筆書きはできない。 証明 一筆書きが可能なグラフで、奇数点が奇数個あると仮定すると、 奇数点を2組ずつとると、必ず1個奇数点が余る。この奇数点は 一筆書きできないので、仮定が誤りである。