18世紀のプロイセンの町ケーニヒスベルクでは、町の真ん中をプレーゲル川が流れていて、川の中には2つの島がありました。そして、島どうしや島と両岸を結ぶ橋が全部で7つありました。町の人々の間には、昔から「7つの橋をそれぞれちょうど1回ずつ渡って、全部を渡りきることはできるだろうか?」という疑問がありました。散歩好きの市民たちが実際に何度も試しましたが、成功した人は1人もいませんでした。

1736年、数学者レオンハルト・オイラーがこの疑問にはっきりとした答えを出しました。ただし、オイラーは自分で橋を渡りに行ったわけではありません。問題を思いきり単純にしたのです。陸地(両岸と島)をそれぞれ点に、橋をその点どうしを結ぶ線に置きかえました。こうしてかくと、ケーニヒスベルクの問題は「えんぴつを紙からはなさず、同じ線を2回なぞらずに、この図形をかけるか?」という「一筆書き」のパズルになります。このアイデアこそが、いまグラフ理論とよばれている数学の分野の出発点でした。

3 5 3 3 4つの陸地すべてで橋の数が奇数→不可能
円の中の数は、その陸地につながる橋の数(次数)です。5、3、3、3と、すべて奇数です

ここで大切なのが次数という考え方です。1つの点(陸地)につながっている橋の数を、その点の次数といいます。一筆書きの途中で点を通りぬけるときは、入ってくる橋1つと出ていく橋1つを、必ずペアで使います。だから、出発点でも終点でもない点では、通るたびに橋を2つずつ使っていくことになり、その点の次数は必ず偶数でなければなりません。

反対に、次数が奇数の点になれるのは、2つのうちどちらかだけです。旅が始まる出発点(出ていく橋が1つ余る)か、旅が終わる終点(入ってくる橋が1つ余る)です。だから、グラフ全体で次数が奇数の点は多くても2個までです。奇数の点が0個なら、どこから始めても全体を一筆で書けて、出発点に戻ってくることもできます。奇数の点がちょうど2個なら、その2点を出発点と終点にしたときだけ書けます。でも奇数の点が3個以上あると、全部を出発点か終点にすることはできないので、一筆書きはどうやっても不可能です。

ケーニヒスベルクの4つの陸地は、まさにこのわなにはまっていました。1つの島には5つの橋が、残り3つの陸地にはそれぞれ3つの橋がつながっていて、5、3、3、3です。4つの陸地すべての次数が奇数なのです。奇数の点が4個もあるので、町の人々がどんな順番で試しても、7つの橋をちょうど1回ずつ渡ることは、最初から数学的に不可能だったのです。

オイラーはこのひとつの問題から、点と線でできたつながりを研究するグラフ理論を生み出しました。このアイデアは、いまでは私たちの暮らしのあちこちで使われています。地図アプリが最短経路を見つけるしくみも、SNSが友達関係を分析するしくみも、インターネットでデータの通り道を決めるしくみも、すべてグラフ理論で動いています。300年前に川辺を散歩していた人々の小さな好奇心が、私たちが毎日使っている技術の根っこになったのです。

アクティビティのページでは、ケーニヒスベルクの橋の地図を実際にクリックしながら一筆書きに挑戦できます。ほかの図形でも練習して、どれができてどれができないのかを自分で確かめられます。最後には、それぞれの図形の次数の表を見て、次数が奇数の点を数えるだけで答えが前もってわかることを確かめられます。