昨日の問いの簡単な解説
殆どのテキストでは『一筆書きできる必要十分条件は奇点の個数が０または２であること』と記述されていると思いますが、問題の意味が分らない方もいるかと思いますので用語説明をしますね。
まず、奇点とは各頂点の次数の数、つまり、各頂点から出ている辺（線）の数が奇数個ある点っていう意味です。
更に、必要十分条件とはこの場合
(1)必要条件が『一筆書きできれば奇点の個数は０または２である』で、
(2)十分条件は『奇点の個数が０または２であれば、一筆書きができる』です。
では、まずは(1)から証明してみましょう。
これは簡単です。
もし仮に一筆書きができたとし、その道筋はもとの点になる場合と他の点で終る場合に分かれます。 つまり、始点終点が一致するか否かってことですから、その道筋の途中の点を考えると、その点に入る辺と出る辺が付いていますよね。 したがって、この点の次数は偶数になることが分ります。 よって、出発点と到着点が同一でないときは、２つの奇点があることになります。
次に、(2)の証明に移りたいと思いますが、少々これは厄介かと思われますので数学的帰納法で証明しますね＾＾；
まず、辺の個数をmとします。 m=1のグラフにおいて、グラフは閉じている（奇点０個）か開いているか（奇点２個）によって二通り得られますが、いずれも一筆書きできます。 では、辺の数m-1以下のグラフでは一筆書きできたとし、辺の数mのグラフを考えてみます。(i)奇点の個数が０の場合１つの辺を取り除くと、奇点となる点が２つ存在します このグラフは、２つに分かれることはなく連結性は保たれています。 なぜならば、仮に２つの部分に分かれたとすると、それぞれの点は別々の部分に入り、それぞれの部分のグラフには奇点が一個ずつ入ることになります。 よって、これは、『次数の総和が常に偶数』であるっていう定理に反します。 故に、m-1のグラフでは一筆書きができ最後に取り除いた一本を付け加えると全体の一筆書きが完成することになります。(鄱)奇点の個数が２の場合点の個数が２の場合は明らかに成立することがわかりますから、点の個数が３以上の場合で考えてみます。 これも先程の(i)での辺の除去から出発するのと同様に考えれば、証明できますので、ここでは省略したいかと思います。 以上より、一筆書きできることが証明なされました。
