高校数学C 一筆書きの条件—つながりと奇数次数の頂点から可否を判断する｜武蔵野個別指導塾

離れた輪と孤立点を含む図で連結性を調べ、奇数次数の頂点と実際の通過列から一筆書きの可否を判断します。

よくあるのは、理系の高3が奇数次数の頂点だけを数え、辺の集まりが離れていることを見落とす場面です。偶数次数の頂点ばかりなら元の場所に戻れそうですが、離れた別の部分へは線を通って移れません。次数の表に丸を付ける前に、描かれた線がどのようにつながっているかを確かめます。

何を判定するのか

一筆書きとは、ペンを紙から離さず、各辺をちょうど1回ずつ通ることです。頂点は複数回通ってかまいません。すでに通った辺を逆向きにたどることも2回目になるため認めません。始点と終点が異なるものを開いた一筆書き、同じものを閉じた一筆書きと呼びます。

問われ方には、与えられた図の可否と始点・終点を答える型、辺を1本加えたときの変化を調べる型、離れた部分や孤立点を含めて条件を見直す型があります。どの場合も、まず辺を持つ頂点どうしが辺をたどって行き来できるかを調べます。次に各頂点の次数を数えて奇数の頂点の個数を調べます。辺がない頂点は孤立点と呼び、辺を通る一筆書きの連結性の判定から除きます。

ここでは辺に向きがない図を扱い、同じ2頂点を結ぶ重複した辺とループは設けません。線が交差していても、そこに頂点があると指定されていなければ接続しません。辺が1本もない図については始点や通過の約束が別途必要なので、以下では少なくとも1本の辺があるものとします。

頂点での出入りと偶奇

頂点の次数は、その頂点に接続する辺の本数です。図1のように、途中で頂点に入ったなら、まだ通っていない別の辺から出ます。入る辺と出る辺が1組になるため、始点でも終点でもない頂点の次数は偶数です。頂点を何回訪れても、訪問ごとに2本ずつ対応します。

図1の途中の頂点では2本が1組です。開いた一筆書きの始点には最初に出る辺が1本余り、終点には最後に入る辺が1本余ります。したがって始点と終点は奇数次数で、ほかは偶数次数です。閉じた一筆書きでは始点と終点が同じなので、そこでも出る辺と入る辺が組になり、各頂点は偶数次数です。

逆に、辺を持つ部分が連結で、奇数次数の頂点が0個なら閉じた一筆書きができます。奇数次数の頂点が2個なら、それらを始点と終点にして開いた一筆書きができます。奇数次数が4個以上なら一筆書きはできません。なお、次数の和は各辺を両端で1回ずつ数えた値なので偶数です。そのため奇数次数の頂点の個数は偶数となり、1個や3個という数え方が出たら辺の数え漏れを探します。

連結性が必要な理由は、ペンを離さずに通る辺の列では、次の辺が現在いる頂点に接していなければならないからです。離れた辺の集まりには移れません。逆向きの主張も、単なる小さな例の一致ではなく次のように説明できます。

偶数次数の連結な図で辺を重ねずに進み、進めなくなるまで続けます。出発点以外にいる間は、そこに入るたびに出入りの2本を組にできるので、未使用の出口が残ります。したがって止まるのは出発点です。まだ辺が残るなら、連結性から、できた閉じた列上の頂点に未使用の辺が接する場所があります。そこから同様に閉じた列を作り、元の列に挿入します。有限本の辺について繰り返すと全辺を使えます。

奇数次数が2個の場合は、その2頂点を結ぶ仮の辺を1本加えると全次数が偶数になります。仮の辺が既存の辺と重なっても別の辺として区別します。上の出入りの議論は重複辺にも適用できるので、閉じた列を作って仮の辺を取り除けば、元の2頂点を端とする開いた列が得られます。これで偶奇と連結性が十分である理由も押さえられます。

基本例題：通路を一筆で歩けるか

地点 A、B、C、D を結ぶ通路が AB、BC、CA、CD の4本あります。通路には向きがなく、交差や他の接続はありません。各通路を1回ずつ通るとき、開いた一筆書きと閉じた一筆書きの可否を答え、可能なら地点の通過列を1つ示してください。

図2のように、三角形の C から D へ1本伸びています。頂点ごとに端を数え、辺の集合も確認します。

A の次数 = 2（AB、CA）
B の次数 = 2（AB、BC）
C の次数 = 3（BC、CA、CD）
D の次数 = 1（CD）
次数の和 = 2 + 2 + 3 + 1 = 8
辺数の2倍 = 2・4 = 8

次数の和と辺数は対応しています。A、B、C は三角形でつながり、D は CD で C につながるので、辺を持つ部分は連結です。奇数次数は C と D の2個です。よって開いた一筆書きは可能で、始点と終点は C と D です。閉じた一筆書きは不可能です。

たとえば C、A、B、C、D の順に進みます。使った辺は順に CA、AB、BC、CD です。指定の4本がそれぞれ1回現れ、始点 C と終点 D は異なります。逆順の D、C、B、A、C も可能です。判定後に通過列を辺の一覧へ戻すと、次数の計算だけで見落とした重複も検出できます。

もし D から C に進んだ後、C から D に戻ると、同じ CD を2回通ります。頂点 C を再訪することは許されますが、辺 CD の再通過は許されません。この違いが、通過列の検査で確認する対象です。

標準例題：離れた輪と孤立点

展示の模型に地点 P、Q、R、S、T、U、V があり、通路は PQ、QR、RP、ST、TU、US の6本です。V には通路が接していません。各通路を1回ずつ通る開いた一筆書きと閉じた一筆書きの可否を答えてください。さらに通路 RS を1本加えた場合も同様に答え、可能なら通過列を1つ示してください。

最初の6本は PQR と STU の2つの輪です。各頂点の次数と、V の扱いを分けて調べます。

P、Q、R の次数 = 2、2、2
S、T、U の次数 = 2、2、2
V の次数 = 0
奇数次数の頂点の個数 = 0

V は孤立点なので連結性の判定から除きます。しかし V を除いても、PQR と STU の間には通路がありません。したがって辺を持つ部分は連結ではなく、開いた一筆書きも閉じた一筆書きも不可能です。奇数次数が0個という条件は満たしても、それだけでは足りません。

次に RS を加えると、2つの輪がつながります。R と S の次数はそれぞれ1増え、ほかの次数は変わりません。

R の次数 = 2 + 1 = 3
S の次数 = 2 + 1 = 3
P、Q、T、U の次数 = 2
V の次数 = 0
奇数次数の頂点の個数 = 2

辺を持つ部分は連結で、奇数次数は R と S です。開いた一筆書きは可能で、閉じた一筆書きは不可能です。R、P、Q、R、S、T、U、S と進むと、RP、PQ、QR、RS、ST、TU、US を順に通ります。元の6本と追加した1本がそれぞれ1回ずつ現れます。V を訪問する必要はありません。問題が「全頂点を訪れる」と別に要求するなら、孤立点 V は訪れられないため、その追加条件は満たせません。

発展例題：辺を加えて条件を変える

地点 A、B、C、D、E を結ぶ辺が AB、BC、CD、DA、AC、CE の6本あります。向きはなく、辺の交差による新しい頂点はありません。まず開いた一筆書きと閉じた一筆書きの可否を答えてください。次に、既存の辺と重ならず異なる2頂点を結ぶ辺を1本加えるとき、閉じた一筆書きが可能になる追加辺をすべて答え、通過列を1つ示してください。

各辺の端から次数を求めます。

A の次数 = 3（AB、DA、AC）
B の次数 = 2（AB、BC）
C の次数 = 4（BC、CD、AC、CE）
D の次数 = 2（CD、DA）
E の次数 = 1（CE）
次数の和 = 3 + 2 + 4 + 2 + 1 = 12
辺数の2倍 = 2・6 = 12

四角形の辺と CE により、辺を持つ部分は連結です。奇数次数は A と E なので、開いた一筆書きは可能、閉じた一筆書きは不可能です。A、B、C、D、A、C、E と進めば、AB、BC、CD、DA、AC、CE を各1回通れます。

辺を1本加えると、その両端の次数だけが1ずつ増え、偶奇が入れ替わります。閉じた一筆書きのためには A と E の両方を偶数にし、ほかの偶数を奇数に変えない必要があります。したがって追加辺は AE に限られます。AE は元の辺の一覧にないので、問題の条件を満たします。

追加後は次数が A で 4、E で 2、B と D で 2、C で 4 です。元の図が連結なので辺を加えた図も連結です。A、B、C、D、A、C、E、A と進めば、AB、BC、CD、DA、AC、CE、EA の7本をそれぞれ1回通り、A に戻れます。

この判断は端点の偶奇を変える効果に基づきます。たとえば B と D を結べば A、B、D、E が奇数となり、一筆書きはできません。A と B を結ぶことは既存の辺との重複で問題の条件に反しますが、仮に区別できる別の辺を許しても、奇数は B と E になり、閉じる条件には届きません。許される辺と、その辺による偶奇の変化を別々に調べることが必要です。

誤答を直す：偶奇が合っていても移れるか

「図3はどの頂点も次数が2だから、閉じた一筆書きができる」という答えを考えます。2つの三角形は交わらず、それぞれが3本の辺でできています。図3のように、片方を一周しても、もう片方へ移る辺はありません。

誤りの原因は、偶数次数を必要条件として使った後、連結性も必要であることを忘れた点です。各輪の中では閉じて歩けますが、図全体の6本を1回ずつ通るには、ペンを離さずに別の輪へ移る必要があります。その移動に使える辺がないため不可能です。

直すときは、1つの辺から出発し、辺をたどって届く頂点を印で囲みます。辺を持つ頂点が囲みの外に残れば、その図全体は連結ではありません。孤立点だけが外に残る場合は、辺の一筆書きの条件には影響しません。この確認を終えてから奇数次数を数えると、判定の根拠を順番に説明できます。

逆の失敗もあります。図がつながっていることを見て、必ず一筆書きできるとする答えです。たとえば1つの中心から4本の辺が別々の端点へ伸びる図では、4つの端点が奇数次数です。中心を通って移動できても、4つの端点を始点と終点の2か所に収められません。連結性と偶奇は別々に確認します。

練習問題

各問の辺は無向で、挙げたもの以外はありません。辺の重複、ループ、新しい交点はないものとします。各問で開いた一筆書きと閉じた一筆書きの可否を答え、可能なときは通過列を1つ示してください。問題5では加える辺も答えます。

1. 辺が JK、KL、LM の3本である図を考えます。
2. 辺が GH、HI、IJ、JG の4本である図を考えます。
3. 辺が AB、AC、AD の3本である図を考えます。
4. 辺が WX、XY、YW、ZV の4本である図を考えます。
5. 辺が PQ、QR、RS、SP、PR の5本である図を考えます。既存の辺と重ならず異なる2頂点を結ぶ辺を1本加え、閉じた一筆書きを可能にしてください。

練習の答えと解き方

1. 次数は J と M が1、K と L が2です。連結で奇数次数が J と M の2個なので、開いた一筆書きは可能、閉じた一筆書きは不可能です。J、K、L、M と進めば JK、KL、LM を各1回通ります。

2. 各頂点の次数は2です。4本の辺で連結なので、閉じた一筆書きが可能です。奇数次数がないため、異なる端点を持つ開いた一筆書きは不可能です。G、H、I、J、G の列は GH、HI、IJ、JG を1回ずつ通って戻ります。

3. A の次数は3、B、C、D の次数はそれぞれ1です。図は連結ですが、奇数次数が4個あるため開いたものも閉じたものも不可能です。3本の辺はすべて中心 A に集まり、端点のうち2個以上を途中で通り抜けることができません。

4. W、X、Y の次数は2、Z、V の次数は1です。奇数次数が2個でも、三角形と辺 ZV は離れています。辺を持つ部分が連結でないので、開いたものも閉じたものも不可能です。片方で通る辺の列から他方へ続ける接続がありません。

5. P と R の次数は3、Q と S の次数は2です。元の図は連結で、奇数次数が P と R の2個なので、開いた一筆書きは可能、閉じた一筆書きは不可能です。P、Q、R、S、P、R と進むと PQ、QR、RS、SP、PR を1回ずつ通ります。閉じるには奇数の2頂点 P、R の偶奇をともに変える必要がありますが、PR は既存の辺です。ほかの1本を加えても両方を同時に偶数にできないため、指定条件で可能にする追加辺はありません。

問題5では、加えることができる辺を探す前に必要な端点を絞りました。必要な辺がすでに存在するという失敗の場合も、条件の一部です。重複を許す別の問題なら2本目の PR を区別して加える選択が生じますが、ここでは許されません。

覚えておくこと

辺を持つ部分の連結性を先に確かめます。 奇数次数が0個なら閉じた一筆書きが可能です。 奇数次数が2個なら、その2頂点を端とする開いた一筆書きが可能です。 奇数次数が4個以上、または辺を持つ部分が非連結なら不可能です。 可能な場合も、通過列を辺の一覧に戻して1回ずつか確かめます。

つまずきの見分け方

次数の数え間違いか連結性の見落としかは、答えだけでは区別できません。個別指導では、各頂点に接する辺の名前を並べた記録と、たどって到達できる頂点に付けた印を確かめます。次数の和が辺数の2倍に合わなければ、辺の両端を再確認します。和が合っても次数を別の頂点に付け間違えた可能性があるため、各辺の端点まで照合します。

通過列がある場合は、隣り合う頂点の組を辺の一覧と突き合わせます。存在しない辺への移動、同じ辺の再使用、残った辺を区別できれば、判定と構成のどちらで止まったかが見えます。線がつながる範囲と、端点に残る奇数の数が、一筆書きの可否を決めます。