全ての線を一度ずつ通る一筆書きは、描く前に判定できます。線がひとまとまりにつながっていることを確かめた上で、奇数本の線が集まる点が0個または2個なら可能です。0個なら出発点へ戻れ、2個ならその二つが出発点と終点になります。
線の長さより、つながり方を見る
ここでいう一筆書きは、ペンを紙から離さず、全ての線をちょうど1回なぞることです。同じ点へ何度戻っても構いませんが、同じ線を往復することはできません。曲線でも直線でも、長くても短くても、判定に使うのは接続の関係です。
線の端や分岐点を「頂点」、頂点の間を結ぶ線を「辺」と呼びます。ある頂点につながる辺の本数が、その頂点の「次数」です。一直線の途中に印を付けて頂点を一つ増やしても、そこは次数2なので、判定の偶奇には影響しません。自分へ戻る輪の辺は、同じ頂点へ二つの端が接続するため、次数に2を加えます。
途中の点では「入る」と「出る」が対になる
線を描いている途中である頂点へ入ったら、まだ描いていない別の線から出なければなりません。入る線と出る線は2本で一組です。何度その点を訪れても、この組を繰り返すので、途中の頂点には偶数本の辺が必要になります。
例外になれるのは、最初に入らずに出発する点と、最後に出ずに終わる点だけです。出発点と終点が異なるなら、その二つの次数が奇数。出発点に戻るなら、そこでも最初に出た線と最後に入った線が組になるため、全て偶数です。奇数の点が4個以上あると、出発点・終点だけでは処理できません。
この説明から、「次数が大きい点があるから難しい」とは限らないことも分かります。6本集まる点なら3組を作れますが、3本集まる点は1本余ります。大切なのは本数の大小ではなく、偶奇です。
奇数が少なくても、離れていたら描けない
離れた三角形を二つ描いた図を考えます。全ての頂点の次数は2で、奇数の頂点は一つもありません。それでも、片方の三角形からもう片方へ移るには、ペンを離すか新しい線を描く必要があります。
したがって、奇数の個数だけでなく、辺を持つ全ての頂点が一つにつながっていることが必要です。線につながっていない孤立した点は、今回の「全ての線を通る」という問題からは除いて考えます。この連結性の条件を忘れると、見かけ上の反例を作ってしまいます。
条件を満たせば、なぜ描けるのか
全て偶数でつながった図なら、未使用の線を順にたどると、途中の点だけで行き詰まることはありません。入るたびに、対となる出る線が残るからです。まず出発点へ戻る輪ができます。まだ使っていない線があれば、既にできた輪のどこかから別の輪をたどり、それをつなぎ込みます。これを繰り返せば全ての辺を取り込めます。
奇数の頂点が二つの場合は、その二つを一時的な線で結んだと考えます。すると全頂点が偶数になるため、全てを一周できます。最後に一時的な線を取り除いて、その場所で輪を開けば、一方の奇数頂点から他方へ至る一筆書きになります。これが「必要条件」にとどまらず「十分条件」でもある理由です。
家の形を実際にたどる
図の左の家形では、奇数なのはEとCです。例えばE→A→B→C→D→E→Cと進むと、6本の辺を全て一度ずつ通れます。中央の図で対角線A–Cを追加すると、奇数頂点はAとEへ変わります。今度はA→B→C→D→E→A→C→Eとたどれます。
交差点では、線が実際につながっていて曲がれるのか、それとも橋のように上下に通過するだけなのかを決めて下さい。同じ絵でも、この約束が違えば別のグラフになります。また「全ての頂点を一度ずつ訪ねる」問題はハミルトン路という別の問題であり、今回の偶奇判定はそのまま使えません。
参考資料
- University of Cambridge NRICH「Eulerian」：一筆書きと奇数次数の点
- Sedgewick・Wayne・Liu「EulerianPath.java」：連結性・次数条件とオイラー路の構成・検証
資料確認日：2026年10月2日。本文の数値例・模式図は、特記したものを除き本記事の説明用に作成しています。