ケーニヒスベルクの橋の問題とは？わかりやすく｜オイラーが1736年に解いた一筆書き・奇数点の数え方

ケーニヒスベルクの橋の問題とは？（ひとことで）

ケーニヒスベルクの橋の問題とは、「町じゅうにかかる7本の橋を、どれも1回だけ渡って、元の場所にもどってこられるか」という問題です。18世紀の初め、プロイセン王国の町ケーニヒスベルク（今のロシア連邦カリーニングラード）で、市民のあいだの遊びとして語られていました。

この問題を1736年ごろに解いたのが、スイスの数学者レオンハルト・オイラーです。答えは「できない」。オイラーは橋の配置を調べつくすかわりに、陸地を「点」、橋を「線」に置きかえて、「奇数本の線が集まる点がいくつあるか」だけを数えれば答えが決まることを示しました。これが、今の一筆書きの判定法です。

この考え方は、のちに点と線のつながりだけを研究するグラフ理論（四色問題もその仲間です）と、形そのものではなく「つながり方」を調べる位相幾何学の出発点になりました。小学校の「一筆書きパズル」は、約290年前のこの問題とつながっているのです。

橋の問題の意味をやさしく解説

町のようす：川と4つの陸地と7本の橋

ケーニヒスベルクの町には、プレーゲル川が流れていて、町は川で4つの陸地に分かれていました。ここでは、北岸をB、南岸をC、川の中の島（中州）をA、東の陸地をDとよびます。そこに7本の橋がかかっていました。

問題は、「どこから出発してもよいので、7本の橋を1回ずつ、ちょうど渡りきれるか」です。「元の場所にもどる」条件をつけた形で語られることもありますが、オイラーは「もどらなくてもよい」場合も調べて、どちらも不可能だと示しました。

決まりは3つだけ

• 橋は1回しか渡れない：同じ橋を2回渡ってはいけません。
• 全部の橋を渡る：1本でも渡らない橋があってはいけません。
• 橋以外では川をこえない：船で渡ったり、泳いだりしてはいけません。

地図を「点と線」に置きかえる

ここで大事なのは、橋の長さや陸地の広さは関係ないということです。必要なのは、「どの陸地が、どの陸地と、何本の橋でつながっているか」だけ。そこで、陸地を点、橋を線に置きかえます。こうしてできた「点と線の図」をグラフといいます（グラフ用紙のグラフとは別のものです）。

すると問題は、「この図を、同じ線を2回通らずに、1回の筆づかいでなぞれるか」という、一筆書きの問題になります。座標の考え方や長さを使わず、「つながり方だけ」を調べるのが、この問題の新しいところでした。

用語：次数と奇数点・偶数点

グラフの点に集まっている線の数を、その点の次数といいます。次数が奇数とはの点を奇数点、偶数とはの点を偶数点とよびます。ケーニヒスベルクのグラフでは、A が5、B・C・D が3なので、4つの点がすべて奇数点です。このことが、答えを決めます。

橋の問題の歴史と年表

町の人びとの遊びだった

ケーニヒスベルクは、バルト海に近い、プロイセン王国の中心的な都市でした。この町の人びとのあいだで、「日曜日の散歩で、7本の橋を1回ずつ渡れないものか」という話題があった、と伝えられています。だれもできた人はいませんでしたが、「できない」と証明した人もいませんでした。

町の名前と有名な住人

ケーニヒスベルクは、ドイツ語で「王の山」という意味の町の名前です。哲学者のカント（1724年生まれ）が、生涯のほとんどをこの町で過ごしたことでも有名です。カントは毎日同じ時刻に散歩をしたため、町の人びとが時計がわりにした、という逸話も伝えられています（諸説あります）。また、ゴールドバッハ予想で知られるゴールドバッハも、この町の生まれです。橋には、「鍛冶屋の橋」「蜜の橋」「緑の橋」などの名前がついていた、とされています。数学の歴史に名を残す問題が、散歩好きの町で生まれたのは、ふしぎな偶然です。

1735〜1736年：オイラーが「できない」ことを示す

ロシアのサンクトペテルブルクの科学アカデミーにいたオイラーは、ダンツィヒ市長カール・エーラーなどから、この問題について手紙で尋ねられた、とされています。オイラーははじめ「これは数学の問題というより、ものの考え方の問題だ」という趣旨の返事をしたと伝えられていますが、やがて考えを変え、解決しました。1735年8月26日にアカデミーで発表し、論文は1741年に出版されています（論文の題は、ラテン語で「位置の幾何学に属する一つの問題の解」）。

オイラーは、ライプニッツの業績が構想した「位置の幾何学」（長さや大きさではなく、位置関係だけを調べる幾何学）の例として、この問題を位置づけました。

オイラーの書いた「文字ならべ」

オイラーは、渡る順番を、通る陸地の文字をならべて書き表しました。たとえば A→B→D→C→A…のように。7本の橋を全部渡る道すじなら、文字は8個（橋の数＋1）ならびます。ところが、5本の橋が集まる A は道すじに3回、3本ずつの B・C・D は2回ずつ出るはずで、合計は9個になり、8個と合いません。これでは矛盾するので、全部の橋を1回ずつ渡る道すじはありえないと分かります。

その後：条件の「逆」の証明

オイラーは「奇数点が3つ以上あると一筆書きできない」ことを示し、逆に「奇数点が0個か2個で、図がひとつながりなら一筆書きできる」ことも述べました。ただし、この逆の部分（十分条件）の証明をきちんと書いたのは、ドイツの数学者カール・ヒーアホルツァーで、その論文は1873年に（本人の死後に）出版された、とされています。

橋の問題はいつ・だれが解いた？

橋の問題は、1736年ごろ、スイスのバーゼル出身の数学者レオンハルト・オイラーが解きました。答えは「7本の橋を1回ずつ全部渡ることは、できない」です。

オイラーの答え：奇数点の数がカギ

オイラーの考えを、現代の言葉で説明しましょう。一筆書きの道すじで、ある点を途中で通りすぎるとき、その点には「入ってくる線」と「出ていく線」の2本を使います。つまり、途中の点では、使う線の数はいつも偶数（2本ずつ）です。

• 点が偶数点なら：入って、出て、入って、出て…とくり返して、すべての線を使いきれます。
• 点が奇数点なら：入って出るをくり返すと、最後に1本だけ余ります。この余った1本は、その点が「出発点」か「ゴール」のときにしか使えません。

出発点とゴールは、それぞれ1か所ずつしかありません。だから、奇数点は多くても2つまでです。

判定のルール（まとめ）

奇数点の数	一筆書きは？	書き方
0個	できる	どの点から始めても、元の点にもどる
2個	できる	一方の奇数点から始めて、もう一方の奇数点で終わる
4個以上	できない	（2個をこえる分は、どうしても余る）

ただし、これは図がひとつながりである（バラバラに分かれていない）ときの話です。また、奇数点の数が1個や3個になる図は、存在しません。その理由は、あとの練習問題で考えてみましょう。

ケーニヒスベルクの場合

ケーニヒスベルクのグラフは、4つの点がすべて奇数点（5・3・3・3）でした。奇数点が4個あるので、一筆書きはできません。出発点とゴールを別の場所にしても、奇数点が2個余ってしまいます。だから、「元にもどる」条件をなくしても、答えは変わりません。

用語：オイラー路とオイラー閉路

グラフの線を、1回ずつ全部通る道をオイラー路といいます。とくに、出発点にもどってくるものをオイラー閉路（オイラー回路）とよびます。奇数点が0個なら閉路、2個なら閉路ではない路、と覚えましょう。ケーニヒスベルクのグラフには、どちらもありません。

一筆書きの解き方の手順

1. 図のすべての点に、集まる線の数を書き込みます。
2. 奇数の点の数を数えます（0個か2個なら、一筆書きできます）。
3. 2個のときは、奇数点のどちらかから出発します。0個のときは、どの点からでもかまいません。
4. ゴールまで進みます。途中で、あとでもどれなくなる線（橋のように、渡ると元の部分に二度と戻れない線）を先に通らないように注意します。

この手順で、図が複雑でも、確実に答えが出せます。実際に書くときは、最初に全部の線の数を数えておくと、「いつまで書いてもゴールにつかない」という失敗を防げます。数え終わったら、通った線に印をつけながら進むと、通り忘れも防げます。

橋を1本へらしたら？

もし A と B を結ぶ橋が1本だけだったら、どうなるでしょう。A は4本、B は2本の偶数点になり、奇数点は C と D の2つだけです。この場合は、C から出発して D で終わる一筆書きができます。実際、橋を取りのぞいた町では「全部の橋を1回ずつ渡る散歩道」が作れるのです。

橋の問題はなぜ難しかったのか

1. 全部の道を試す方法では、きりがない

7本の橋の渡り方を全部調べると、数が多くなります。もっと橋の数が多い町では、人の手では調べきれません。「できない」ことを示すには、すべての場合にあてはまる理由を見つける必要があります。これは、背理法とはのように、「もしできたとしたら矛盾する」と示す考え方と、よく似ています。

2. 「何に注目するか」が分からなかった

当時の数学者は、距離や面積、角度など、長さや大きさを調べるのが数学だと考えていました。橋の問題は、橋の長さにも陸地の形にも関係がありません。オイラー自身も、手紙の中で、この問題は「ふつうの幾何学や計算の問題ではない」という趣旨のことを書いた、と伝えられています。「何を無視してよいか」を見きわめることが、いちばんの難しさでした。

3. 新しい種類の数学が必要だった

この問題を解くには、長さを使わない新しい種類の数学が必要でした。オイラーは、その新しい数学を、ライプニッツの構想した「位置の幾何学」の形で示したのです。のちに、この分野は位相幾何学（トポロジー）に育ちます。ポアンカレがその基礎を大きく広げました。

4. 「ふつうの数学」と見なされなかった

オイラーほどの数学者でも、この問題が数学の問題かどうかで、最初はまよったと伝えられています。数式も、図形の計算も出てこない。それでも、きちんとした証明で「できない」と言える。こうして、数学とは「数や図形の計算」だけではなく、「ものごとのつながり方の理由を見つけること」でもある、という見方が広がりました。この考え方は、のちのカントールの集合論やヒルベルトの公理主義の時代の数学にも、受けつがれていきます。

よくある誤解

「橋を1本足せばできるようになる」と思う人がいますが、これは場合によります。橋を1本足すと、その橋の両端の2つの点の次数がそれぞれ1ふえます。たとえば B と C を橋で結ぶと、B と C は4本ずつの偶数点になり、奇数点は A（5本）と D（3本）の2つだけになります。すると、A から出発して D で終わる一筆書きができるようになります。実際には、「どこに橋を足すか」で結果が変わるのです。

受験・勉強と橋の問題のつながり

中学受験：一筆書きの問題

中学受験の算数では、「次の図形を一筆書きできるものはどれか」「一筆書きできるように1本線を足す／けずる」といった問題がよく出ます。解き方はいつも同じで、各点に集まる線の数を数え、奇数点の数を調べるだけです。

星形の図形、たくさんの円がつながった図、正方形の中に対角線を引いた図など、見た目は複雑でも、「奇数点が0個か2個か」を数えれば、答えが決まります。数え間違いを防ぐため、点ごとに線の数を書き込むのがコツです。

中学・高校：立体と多面体のつながり

立方体の頂点・辺・面の数については、角柱・角錐の辺・面・頂点の数で学びます。さらに、オイラー自身が見つけたオイラーの多面体定理（頂点−辺＋面＝2）も、点と線の考え方でとらえられます。立方体の骨組みは、頂点8個すべてに3本ずつ辺が集まるので、一筆書きはできません。

大学受験・大学：場合の数とグラフ

道順の数を数える問題（順列・組合せの公式や、樹形図の使い方）は、グラフの上を歩く問題と考えられます。大学の数学では、グラフ理論は離散数学として学びます。情報科学では、ネットワークの設計や最短経路の探索に欠かせません。

勉強法として：「条件を数えるだけ」にする

橋の問題から学べるのは、複雑な問題を、本質だけの形に置きかえる力です。入試でも、図や文章が複雑なとき、「何が関係していて、何が関係ないか」をまず整理するのが、近道になります。数学の勉強の進め方は、数学の勉強法（解法の暗記→演習→過去問）を参考にしてください。パズル好きな人は、数学オリンピックの問題にも挑戦してみましょう。

例題：線を1本足して一筆書きにする

次のような問題を考えてみましょう。「長方形に、2本の対角線を引いた図があります。この図は一筆書きできません。線を1本だけ足して、一筆書きできるようにするには、どこに足せばよいですか。」

まず、4つの頂点に集まる線の数を数えます。各頂点には、長方形の辺が2本と対角線が1本、合計3本が集まるので、4つの頂点はすべて奇数点です。対角線が交わる中央の点には、4本が集まるので偶数点です。奇数点が4個あるので、このままでは一筆書きできません。

この問題は「足す」かわりに、「1本けずる」と考えると分かりやすくなります。奇数点を2個にへらすには、奇数点どうしを結ぶ線を1本けずるのが近道です。たとえば、長方形の上の辺をけずると、上の2つの頂点は2本ずつの偶数点になり、奇数点は下の2つの頂点だけになります。これで、下の頂点の一方から出発して、もう一方で終わる一筆書きができます。線を足す・けずる問題は、奇数点を2個か0個にすることを目標にすれば、迷わずに解けます。

よくあるまちがい

• 線の数を数えまちがえる：交差している点を、数え落とさないようにしましょう。
• 奇数点が2個のときに、どの点から始めてもよいと思う：奇数点が2個なら、出発点はそのどちらか一方に決まります。
• 図が2つに分かれているのに数える：バラバラの図は、そもそも一筆書きできません。

旅行に使える一筆書き

町の道路を線、交差点を点と考えると、「道路を全部1回ずつ通る」ルートの問題になります。郵便配達や、ゴミ収集車、雪かき車のルートを決めるときの基本的な考え方で、数学では中国人郵便配達問題とよばれています（中国の数学者・管梅谷が1960年代に考えた問題です）。

橋の問題が数学・社会にあたえた影響

• グラフ理論の誕生：橋の問題は、点と線のつながりを研究するグラフ理論の最初の論文とされています。四色問題、P≠NP予想など、現代の難問の多くが、グラフの言葉で語られます。
• 位相幾何学（トポロジー）への道：形の「つながり方」だけを調べる考え方は、リーマンの業績、ポアンカレらを通して、ポアンカレ予想につながっていきます。
• 交通・通信・コンピューター：カーナビの最短ルート、電車の乗りかえ案内、インターネットの通信経路、SNSのつながりの分析まで、グラフ理論は身のまわりの多くの技術の土台です。
• 配送計画・巡回セールスマン問題：すべての町を1回ずつ回る最短のルートを求める「巡回セールスマン問題」は、一筆書きの兄弟のような問題で、いまも研究が続いています。アイルランドのハミルトンの業績が考えた、全部の「点」を1回ずつ通る道（ハミルトン路）も、その仲間です。
• 「一筆書き」と「全部の点を通る道」のちがい：一筆書き（オイラー路）は、奇数点の数を数えるだけで判定できます。ところが、全部の点を1回ずつ通る道があるかどうかは、すばやく判定する方法が知られていません。見た目の似た2つの問題が、むずかしさでは大きくちがうのです。

橋の問題は、今も「ケーニヒスベルクの7つの橋」として語りつがれ。数学を学ぶ人にとって、「問題を見かたを変えて整理する」ことの大切さを教えてくれる、最も有名な例の一つです。

橋の問題に挑戦！練習問題

橋の問題と関係する数学者・難問

• オイラー（橋の問題を解いた人）：グラフ理論の最初の論文を書き、「位置の幾何学」を示しました。
• ライプニッツ：長さや大きさを使わない「位置の幾何学」を構想した人です。
• ハミルトン（ハミルトン路）：全部の点を1回ずつ通る道を考え、イコシアン・ゲームを作りました。
• ケーリー：グラフの「木」の数え上げなど、グラフ理論の初期に貢献しました。
• 四色問題・P≠NP予想・ポアンカレ予想：グラフ理論や位相幾何学とつながる難問です。

ほかの解かれた難問・決着した問題

• 三大作図問題とは（不可能・決められないと証明）
  定規とコンパスだけで、円と同じ面積の正方形・体積2倍の立方体・角の三等分を作図できるか。どれも不可能と証明された
• 平行線公準の問題とは（不可能・決められないと証明）
  ほかの公理から平行線の公理を証明できるか。証明できず、成り立たない幾何学（非ユークリッド幾何学）もあると分かった
• 5次方程式の解の公式とは（不可能・決められないと証明）
  2次・3次・4次方程式のような、四則と累乗根だけの解の公式が5次方程式にもあるか。一般にはないと証明された
• ケプラー予想とは（解決）
  同じ大きさの球をいちばん密に詰める方法は、八百屋のみかんの積み方か。コンピューターで証明
• 四色問題とは（解決）
  どんな地図も4色でぬり分けられるか。コンピューターを使った初めての大きな証明
• 連続体仮説とは（不可能・決められないと証明）
  自然数と実数の「あいだの大きさ」の無限はあるか。今の集合論の公理からは決められないと証明された
• ポアンカレ予想とは（解決）
  穴のない3次元の図形は、球と同じ形と言えるか。ミレニアム懸賞問題で唯一の解決
• ABC予想とは（解決と発表・評価が分かれる）
  a＋b＝c のとき、c は abc の素因数の積よりめったに大きくならない。望月新一の証明は2021年に論文掲載、評価が分かれている

← 前の時代：ケプラー予想とは（解決）　｜　次の時代：ゴールドバッハ予想とは（未解決） →

数学の難問・未解決問題の一覧（いつ・だれが解いたか）　｜　有名な数学者一覧

読みもの（合格大作戦の数学の記事）

• 算数・数学の公式一覧（公式辞典）
  公式・証明・例題を1つずつ
• 数学用語辞典（用語の意味を1語1ページ）
  素数・漸近線など200語
• 数学オリンピックの問題（長方形に詰めた正方形）
  中学生でも解ける本番の問題
• 数学の勉強法（解法の暗記→演習→過去問）
  青・黄・赤チャートの使い分け
• 京大理系数学の出題分析（1999〜2026年度）
  大問別一覧と頻出分野ランキング
• モンティ・ホール問題をわかりやすく
  変えると確率2/3になる理由

よくある質問

あわせて読みたい

• 数学の難問・未解決問題の一覧
• 有名な数学者一覧
• 算数・数学の公式一覧（公式辞典）