4つの 町を A、B、C、D と します。A からは、B、C、D の 3つへ 道みちを ひきます。4つの 町が ぜんぶ 3本ずつ ひくと、3×4で 12本です。でも、A から B への 道みちと、B から A への 道みちは おなじ 1本です。だから 2つずつ かぞえて いました。12÷2で、道みちは 6本です。

ずの まんなかで 2本が ×の かたちに まじわって います。まじわる ところは 町では ありません。ただ、道みちが こうさして いるだけです。

町をA、B、C、Dとします。どの町からも、ほかの3つの町へ道が出ています。町が4つなので、道の数を「3本×4つ」と数えると12です。ところが、AからBへの道とBからAへの道は同じ1本なので、全部2回ずつ数えています。12÷2で、道は6本です。

図の中央で2本が交差していますが、交点は町ではありません。町がn個のとき、同じ考え方で n×(n−1)÷2 本になります。5つなら10本、6つなら15本です。

n個の町のどの2つも道で結ぶ。各町から出る道はn−1本で、合計n(n−1)本になるが、1本の道を両端から2回数えているので、2で割る。道の総数はn(n−1)/2である。n=4なら6本、5なら10本、6なら15本になる。この「どの2点も線で結んだ図」を、グラフ理論では完全グラフと呼ぶ［3］。

グラフ理論では、町を頂点、道を辺と呼び、頂点に集まる辺の数をその頂点の次数と呼ぶ。上の図では、4つの頂点の次数がすべて3である。図の中央の交差は頂点ではない。この次数が、次章の主役になる。

この 6本の 道みちを、どれも 1かいずつ、ぜんぶ あるけるでしょうか。同じ 道みちを 2かい とおっては いけません。紙かみに 図を かいて、ゆびで なぞって みてください。

どの 町から はじめても、うまく いきません。いつも 1本 あまって しまいます。じつは「できない」が こたえです。

わけを いうと、町ごとに 道みちの 数を かぞえます。この ずでは、4つの 町が ぜんぶ 3本です。3は、2でわると 1 あまる 数で、奇数きすうと いいます。一筆書きが できるのは、奇数きすうの 町が 0こか 2こで、ぜんぶが ひと つづきに つながって いる ときだけです。ここでは 4こ あるので、できません。

全部の道を1回ずつ、続けて通る歩き方は、ありそうに見えます。ところが、紙に図を描いて試すと、どの町から出発しても、必ず1本残ります。答えは「できない」です。

理由は、点に集まる線の数にあります。この図では、4つの点のどれにも3本の線が集まっています。3のように2で割ると1余る数を奇数と呼びます。「一筆書きができる」ことと同じなのは、線の数が奇数の点が0個か2個で、図がひと続きにつながっていることです［3］。この図には奇数の点が4個あるので、できません。

同じ辺を2度使わず、全部の辺を1回ずつ通る道を、オイラー路（始点と終点が同じなら、オイラー閉路）と呼ぶ。連結な無向グラフにオイラー路があるための条件は、次数が奇数の頂点が0個か2個であることだ。2個のときは、一方から出発し、もう一方で終わる。0個のときは、どこから出発しても同じ頂点に戻ってこられる［3］。

4つの町を全部結ぶ図（K4）は、4頂点すべての次数が3で、奇数の頂点が4個ある。条件の「0個か2個」に合わないので、オイラー路は存在しない。ここまでで、題名の問いは解けた。次章では、これと同じ形の問題を1735年ごろ解いた、オイラーの話をする。

むかし、ケーニヒスベルクと いう 町が ありました。川かわが 町を 4つの 土地とちに わけて いて、その 4つを 7本の 橋が つないで いました。「7本の 橋を 1かいずつ わたって、もとの 場所へ もどれるか」と、という なぞが あったと つたえられて います。

オイラーは、この 町の 地図ちずを、点と 線せんだけの 図に して かんがえました。土地とちの 形かたちや 橋の 長ながさは、どうでも いいのです。だいじなのは、どこと どこが つながって いるかだけです。

この ずでは、1つの 土地とちに 5本、ほかの 3つに 3本ずつ 橋が あつまります。ぜんぶ 奇数きすうで、4つも あります。だから、1かいずつ わたる ことは できません。4つの 町を ぜんぶ 道みちで むすんだ 図と、おなじ ことが おきて いたのです。

ケーニヒスベルクは、かつてのプロイセンの都市で、川が町を4つの陸地に分けていました。4つの陸地は、7本の橋でつながっていました。「7本の橋を1回ずつ渡って、散歩できるか」という問いがあったと伝えられています。

この問いを解いたのが、オイラーです。1735年8月26日にサンクトペテルブルク科学アカデミーで発表し、論文は1741年に出版されました［1］［2］。オイラーは、陸地を点、橋を線にして、点と線だけの図に置きかえました。陸地の形も橋の長さも関係ありません。どの点がどの点と、何本の線でつながっているかだけが大事です。

この図では、一つの点に5本、残り3つの点に3本ずつ線が集まります。奇数の点が4個です。4つの町を全部結んだ図と、奇数の点の個数が同じなので、一筆書きはできません［2］。

ケーニヒスベルク（現ロシア領カリーニングラード）では、川が町を4つの陸地に分け、7本の橋がそれをつないでいた。オイラーはこの問題を、陸地を頂点、橋を辺とするグラフに置きかえた。1735年8月26日にサンクトペテルブルク科学アカデミーで発表し、論文「位置の幾何学に関する問題の解法」は1741年に刊行された［1］［2］。

次数は、1つの陸地が5、ほかの3つがそれぞれ3で、すべて奇数である。奇数頂点が4個あるので、7本の橋を1回ずつ渡る歩き方はない。Euler Archiveの紹介文は、この論文を、位相幾何学とグラフ理論の初期の仕事とみなすことが多いと述べる［1］。

論文の題にある「位置の幾何学」は、長さや角度を測る幾何学とはちがい、つながり方だけに注目する考え方を指す。ケーニヒスベルクの橋と、4つの町の道は、見た目はまったく別でも、同じ図に置きかえられる。形から「つながり方」だけを取り出すと、別の問題が同じ問題になる。これが、この話のいちばん大きな発見だと思う。

あるいて いる とちゅうの 町を かんがえます。その 町に はいる 道みちが 1本、でて いく 道みちが 1本。とおりぬけるたびに、2本ずつ つかいます。ぜんぶの 道みちを 1かいずつ つかうなら、とおりぬける 町の 道みちの 数は、2本ずつの くみに ならないと いけません。つまり 偶数ぐうすうです。

れいがいは、はじまりの 町と、おわりの 町です。はじまりの 町では、さいしょに 1本 でるぶん、奇数きすうに なれます。おわりの 町も、さいごに 1本 はいるぶん、奇数きすうです。だから 奇数きすうの 町は、はじまりと おわりの 2つだけです。はじまりと おわりが おなじ 町なら、奇数きすうの 町は 0こです。

歩いている途中の点を考えます。その点に入る線が1本、出る線が1本で、通り抜けるたびに2本ずつ使います。全部の線を1回ずつ使うなら、通り抜ける点に集まる線の数は、2本ずつの組になるはずで、偶数です。

例外は、出発の点と到着の点です。出発点では、最初に1本出るので、奇数になれます。到着点も、最後に1本入るので、奇数になれます。だから、奇数の点は出発点と到着点の最大2個です。出発点と到着点が同じなら、全部の点が偶数です。これが「0個か2個」の理由です［3］。

なお、奇数の点の個数は、必ず偶数（0、2、4…）になります。線の数を全部の点で足すと、1本の線を両端で2回数えるので、合計は線の数の2倍になるからです。奇数の点が1個や3個の図は、そもそも描けません［3］。

必要性の証明は短い。オイラー路が頂点vを通り抜けるたびに、vの辺を2本消費する（入る辺と出る辺）。始点でも終点でもない頂点の次数は、2の倍数でなければならない。始点と終点がちがうなら、その2頂点の次数は奇数になる。始点と終点が同じなら、全頂点が偶数になる。したがって、奇数頂点は0個か2個である［3］。

次数の総和は、辺の数の2倍に等しい。1本の辺を両端で数えるからである。総和が偶数なので、奇数頂点の個数は常に偶数になる。この握手の補題を、オイラーは1735年ごろの論文の中で示した［3］。橋の図の奇数頂点が4個で、1個や3個でないのも、これで説明がつく。

では逆に、条件が合えば本当に一筆書きできるのか。オイラーは十分性を述べたが、証明は書かなかった。最初の完全な証明は、カール・ヒールホルツァーのものが、1873年に、彼の死後に発表された［3］。条件が「必要」であることは1735年ごろ、「十分」であることは約140年後に確かめられたことになる。

4つの 町では できませんでした。道みちを 1本 へらして みましょう。A と B を むすぶ 道みちだけ なくすと、A と B は 2本、C と D は 3本に なります。奇数きすうの 町が C と D の 2つなので、できます。C から C→A→D→B→C→D と あるくと、5本ぜんぶ 1かいずつ とおって、D で おわります。

では、町を 5つに ふやして、ぜんぶ 道みちで むすぶと どうでしょう。道みちは 10本で、どの 町にも 4本ずつ あつまります。4は 偶数ぐうすうです。すると、できます。1→2→3→4→5→1→3→5→2→4→1 と あるくと、10本ぜんぶ 1かいずつ とおって、はじめの 町に もどって これます。

町を ふやすほど、むずかしく なるわけでは ありません。町が 3つ、5つ、7つと 奇数きすうなら できます。4つ、6つ、8つの ときは できません。どの 町にも 3本、5本、7本と 奇数きすうの 道みちが あつまるからです。

4つの町では一筆書きできませんでした。道を1本減らすとどうなるでしょう。AとBを結ぶ道だけをなくすと、AとBは2本、CとDは3本になります。奇数の点がCとDの2個なので、できます。C→A→D→B→C→D の順に歩くと、5本を1回ずつ通り、Dで終わります。

では、町を5つに増やして全部を道で結ぶとどうでしょう。道は10本で、どの町にも4本ずつ集まります。全部偶数なので、できます。1→2→3→4→5→1→3→5→2→4→1 と歩くと、10本を1回ずつ通り、出発点に戻ります。

町が3つ、5つ、7つと奇数個なら、どの町にも偶数本の道が集まるので、一筆書きできます。町が4つ以上の偶数個のときは、どの町にも奇数本の道が集まり、奇数の点が町の数と同じだけあるので、できません。町の数が増えても、できるかどうかは単純に決まらず、偶数か奇数かで分かれるのです（町が2つのときは、道1本でできます）。

K4から辺ABだけを除くと、次数はA=2、B=2、C=3、D=3になる。奇数頂点がCとDの2個なので、オイラー路がある。たとえばC→A→D→B→C→Dの順に歩くと、辺CA、AD、DB、BC、CDの5本を1回ずつ通り、Dで終わる。

n個の頂点の完全グラフKnでは、各頂点の次数がn−1である。nが奇数なら次数は偶数なので、オイラー閉路がある。K5は10辺で、1→2→3→4→5→1→3→5→2→4→1がその一例である（始点と終点は1）。nが4以上の偶数なら、次数n−1が奇数で、奇数頂点がn個あるので、オイラー路はない。n=2のときは、辺が1本で奇数頂点が2個なので、一筆書きできる。

ケーニヒスベルクの橋も、本数が変われば次数も変わり、答えも変わりうる。たとえば、奇数頂点どうしを結ぶ橋を1本足すか除けば、奇数頂点は4個から2個に減り、一筆書きができるようになる。

紙かみに、すきな 数の 点を かいて、すべての 点を 線で むすんで みてください。それから、それぞれの 点に 線が 何本 あつまるか かぞえます。ぜんぶが ひと つづきで、奇数きすうの 点が 0こか 2こなら、一筆書きが できるはずです。ゆびで なぞって たしかめましょう。

まわりの もので ためしても おもしろいです。漢字かんじの 形や、じぶんの いえの ちかくの 道みちを 点と 線に して みましょう。かいて いるとき、えんぴつを 紙から はなさないように してください。

紙に好きな図形を描いて、点に集まる線の数を数えてみましょう。線がひと続きにつながっていて、奇数の点が0個か2個なら、一筆書きできるはずです。実際になぞって確かめると、条件の意味が体感できます。星形や、円と十字を組み合わせた図などで試すと、できる図とできない図の差が見えてきます。

もっと知りたくなったら、町を5つ、6つと増やして、全部を道で結んだ図を描き、一筆書きの可否を表にしてみましょう。「線がひと続きか」「奇数の点はいくつか」を数えて予想を立て、実際になぞって確かめます。

確かめる方法として、次の3つがある。①完全グラフKnで、nを変えながら、次数、図がひと続きか、奇数頂点の数、一筆書きの可否を表にする。n=1から8あたりまで調べると、規則性が見える。②図形パズルの「一筆書き」を、次数と連結かどうかで判定してみる。③ケーニヒスベルクの橋の図から、橋を1本増やす・減らすと次数がどう変わるかを調べる。

読む材料としては、オイラーの原論文の紹介（Euler Archive［1］）、橋の数と次数の整理（Wikipedia［2］）、条件と証明の整理（Wikipedia［3］）がある。1735年の発表から、1873年の十分性の証明までの流れを、一次資料から追ってみるのもよい。