18世紀のプロイセンの町ケーニヒスベルクには、川に7つの橋がかかっていました。人々は「すべての橋をちょうど1回ずつ渡って歩くルートはあるだろうか?」と考えました。数学者オイラーがこの問いに答えたとき、グラフ理論というまったく新しい数学の分野が生まれたのです。
陸地をそれぞれ点に、橋を線に置きかえると、下の図になります。点を順番にクリックして、すべての橋をちょうど1回ずつ渡ってみましょう。同じ橋は2回渡れません。何回でも挑戦して、本当にできるのか確かめてみてください。
好きな点をクリックしてスタートし、次の点を順番にクリックして、7つの橋をすべて渡ってみましょう。
図形を選んで、一筆書きに挑戦しましょう。どの図形ならできて、どの図形は絶対にできないのか、自分で確かめてみてください。
1つの点に集まる線の本数を、その点の次数といいます。次数が奇数の点(奇点)がいくつあるかを数えれば、一筆書きができるかどうかが前もってわかります。
奇点が0個 → どこから始めても一筆で書けて、出発点に戻ってきます(オイラー閉路)。
奇点が2個 → 一方の奇点から始めて、もう一方の奇点で終わるときだけ書けます(オイラー路)。
奇点が3個以上 → 一筆書きは絶対にできません。ケーニヒスベルクには奇点が4個あったので、できなかったのです!
線が点を通過するたびに、入ってくる線1本と出ていく線1本を、必ずペアで使います。だから、出発点でも終点でもない点では、1回通るごとに線を2本ずつ使うことになり、その点の線の本数(次数)は必ず偶数になります。
線の本数が奇数になれるのは、出発点(出ていく線が1本多い)と終点(入ってくる線が1本多い)の2種類だけです。だから奇点は多くても2個までです。3個以上あると、全部を出発点か終点にすることはできないので、一筆書きは不可能になります。