高校数学C 頂点の次数—辺の端を数えて次数の和と辺数の関係を確かめる｜武蔵野個別指導塾

交差を頂点に含めるかを見極め、辺の両端を数えて欠けた頂点の次数を求める道筋をたどります。

よくあるのは、理系の高3が線の交差する図を見て、交差の位置にも辺の端があると数えてしまう場面です。紙の上で線が重なることと、そこで辺が分かれることは同じではありません。点の印と問題文を先に確かめてから、各頂点につながる辺を拾うと、数え方を説明できます。辺の端を頂点ごとに集め直すと、次数の和と辺数の関係も見えてきます。

辺の一覧から何を読むか

頂点の次数を問う問題には、図から各頂点の次数を数える型と、次数の和から辺数や欠けた次数を求める型があります。さらに、与えられた次数の組が実際に作れるかを、辺のつながりに戻して調べる型もあります。和の条件を満たすかどうかと、実際に図を作れるかどうかは別々に確かめます。

ここでは向きのない辺を考え、同じ頂点を両端とするループは使いません。同じ2頂点を結ぶ辺も重ねないことにします。点のない交差は頂点ではなく、そこで辺を分割しません。頂点と辺の一覧が与えられたときは、その一覧を図の見た目より優先します。辺の長さや線の曲がり方は次数に影響しません。

頂点に集まる辺の端

頂点は結び目に当たる点、辺は2つの頂点を結ぶ線です。ある頂点を端にもつ辺の本数を、その頂点の次数といいます。どの辺を拾ったかを頂点の横に書くと、交差を余分に拾う誤りを見つけやすくなります。

図1のように、頂点 A に辺 AB、AC、AD が集まるとき、A の次数は3です。各辺は A に1本ずつ接しています。線が途中で別の線と交差しても、交差点に頂点が置かれていなければ、新しい辺の端は増えません。図1では A の周りに3本の辺があり、それぞれの反対側の端は B、C、D です。

辺の端という見方を全体に広げます。ループがないので、1本の辺には異なる2つの端があります。一方の端は一方の頂点の次数に1回、もう一方の端は他方の頂点の次数に1回数えられます。したがって、頂点の次数を全部足した値は、辺の本数の2倍です。

次数の和 = 2 × 辺数
辺数 = 次数の和 / 2

この関係は、連結でない図でも成り立ちます。どの辺も2つの端をもつという事実を、辺ごとに足しているからです。孤立した頂点には接する辺がないので次数は0です。次数の和は必ず偶数ですが、偶数であることだけで、指定された次数の組が実現できるとは限りません。

例えば頂点が4個で辺の重複がないとき、1つの頂点が接続できる相手は最大3個です。したがって次数4の頂点は作れません。和の偶奇が合っていても、この上限や各頂点間の接続を調べる必要があります。以下ではこの区別を具体的に使います。

次数を数える順序を決めると、図が複雑になっても記録を追えます。まず頂点の名前を並べ、次に辺を1本選んで両端の欄に記入します。最後の辺まで処理したら、各欄の項目数を数えます。辺を見て記入する方法と、頂点から線をたどる方法を比べると、同じ誤りを繰り返さずに照合できます。孤立点も一覧から省かず、空欄の本数を0と書きます。

基本例題：交差を通り抜ける2本の辺

4つの頂点 A、B、C、D と、5本の辺 AB、AC、AD、BC、BD を考えます。図2の AC と BD は途中で交差しますが、交差位置は頂点ではありません。各頂点の次数と次数の和を整数で求め、辺数との関係を確かめてください。

図2のように、交差に点を置かず、各辺を名前の付いた両端までたどります。線が交わる位置で辺を切ると、問題文の5本とは別の図になってしまいます。

A に接する辺は AB、AC、AD なので次数は3です。B には AB、BC、BD が接するので3です。C には AC、BC の2本、D には AD、BD の2本が接します。したがって次数は順に 3、3、2、2 です。

次数の和 = 3 + 3 + 2 + 2
         = 10
辺数の2倍 = 2 × 5
          = 10

和が一致する理由を、辺の一覧に戻して確かめます。AB は A と B に1回ずつ、AC は A と C に1回ずつ数えられます。AD、BC、BD もそれぞれ両端に1回ずつ数えられ、5本から合計10個の端が得られます。次数の和はこの10個を頂点別に集計した値です。

仮に交差位置を新たな頂点 E とするなら、AC は AE と EC、BD は BE と ED に分かれます。その場合は辺が7本になり、E の次数は4です。元の4頂点の次数は変わらず、和は14で、7本の2倍です。ただしこれは問題で与えた図とは異なる条件です。交差を頂点とするかどうかは、計算の途中で勝手に変えられません。

標準例題：欠けた次数を復元する

展示室の通路を表す無向グラフに、頂点 P、Q、R、S、T の5個と辺7本があります。ループと重複する辺はありません。P、Q、R、S の次数が順に 3、3、2、2 のとき、T の次数を整数で求めてください。さらに、その次数を実現する辺の組を1組示してください。

次数の和を先に辺数から求めます。T の次数を x とすると、各頂点の次数の和は 3 + 3 + 2 + 2 + x です。

次数の和 = 2 × 7
         = 14
3 + 3 + 2 + 2 + x = 14
10 + x = 14
x = 4

答えは4です。計算した数が実際の接続に戻せることも確かめます。5頂点で次数4の T は、他の4頂点すべてに接します。まず TP、TQ、TR、TS を置くと、P、Q にそれぞれあと2本、R、S にそれぞれあと1本必要です。

残りの辺を PQ、PR、QS とします。P は T、Q、R に、Q は T、P、S に接するのでともに次数3です。R は T、P に、S は T、Q に接するのでともに次数2です。T は4本に接し、辺数は最初の4本と残りの3本で7本です。いずれも異なる2頂点を結び、重複もありません。

次数の和から x を出しただけでは、この辺の配置まで決まりません。実際、残りの3本を PQ、PS、QR としても同じ次数を実現します。次数は各頂点に何本接するかを表しますが、相手の組合せを一意に決める情報ではありません。

発展例題：和が合っても作れるとは限らない

頂点 U、V、W、X の4個からなる、ループも重複辺もない無向グラフを考えます。次数がこの順に 3、3、1、1 となる図が作れるか判定し、理由を述べてください。作れない場合は、どの条件が食い違うかを示してください。

まず次数の和は次のように偶数です。

3 + 3 + 1 + 1 = 8
8 / 2 = 4

辺数が4本なら和の条件は満たします。しかし、この条件だけで図が存在すると決めてはいけません。U の次数が3なら、他の3頂点 V、W、X の全部に接します。V の次数も3なので、U、W、X の全部に接します。

U に必要な辺: UV、UW、UX
V に必要な辺: UV、VW、VX
W に接する辺: UW、VW
X に接する辺: UX、VX

すると W と X はそれぞれ少なくとも2本の辺に接します。指定された次数1に反するので、求める図は作れません。和から得た4本という候補も、実際に必要になった辺 UV、UW、UX、VW、VX の5本と食い違います。

この例の判定は偶数という条件の否定ではありません。偶数であることは必要ですが、それだけでは足りないということです。次数3の頂点が相手を全部使うことから、残りの頂点に必要以上の辺が集まるとわかりました。図を描く場合も、線を足すたびに両端の残り次数を同時に減らすと、この矛盾を見逃しにくくなります。

誤答を端に戻して直す

基本例題で「交差点を含めて次数の和は14、辺数は5本」とした答案を考えます。図3のように、交差点を頂点として4本分を加えた一方で、元の AC と BD はそれぞれ1本のまま数えています。次数の和14と辺数の2倍10が合わないのは、この数え方が混ざっているためです。

修正は、まず点の有無と問題文に戻ることです。交差が頂点でない元の条件なら、AC と BD はそれぞれ1本で、交差位置に次数はありません。4頂点の次数の和は10です。交差を頂点とする別の条件なら、2本の辺をそれぞれ2本に分け、辺数を7本に直して和14と対応させます。図3の左右はこの2つの異なる約束です。

別の誤りとして、次数の和が奇数なのに、そのまま2で割って辺数を小数で答えることがあります。辺数は本数なので整数です。和が奇数なら、ループなしの無向グラフという条件の下では、数え漏れか与えられた条件の矛盾を点検します。与えられた次数が正確であると指定されていれば、該当する図は存在しません。

逆に、和が偶数で辺数が整数になっても、そこで点検は終わりません。発展例題のように各頂点の接続が矛盾する場合があるからです。和の点検は誤りを見つけるための強い手掛かりですが、辺の一覧に戻す作業も必要です。

練習問題

いずれも向きのないグラフで、ループと重複辺はありません。答えは整数で表し、存在を問う問題では理由も示してください。

1. 頂点 A、B、C、D、E に対し、辺が AB、AC、AE、BC、CD、DE の6本あります。各頂点の次数とその和を求めてください。
2. 頂点が6個、辺が8本あります。5頂点の次数が 1、2、3、3、4 のとき、残る1頂点の次数を求めてください。
3. 5頂点の次数が 4、2、2、1、1 です。辺数を求め、条件を満たす辺の組を1組示してください。
4. 4頂点の次数が 3、2、2、2 となるグラフは存在しますか。理由を述べてください。
5. 5頂点の次数が 4、4、1、1、0 となるグラフは存在しますか。次数の和に加えて接続を調べてください。

解答と解き方

1. A には AB、AC、AE の3本、B には AB、BC の2本、C には AC、BC、CD の3本が接します。D には CD、DE の2本、E には AE、DE の2本が接します。

次数 = 3、2、3、2、2
次数の和 = 3 + 2 + 3 + 2 + 2
         = 12
辺数の2倍 = 2 × 6
          = 12

辺の一覧に戻ると、6本の各辺が両端で1回ずつ数えられています。図を描き替えたときに線が交わっても、頂点の追加を指定していなければ次数は変わりません。

2. 残る次数を x とすると、

1 + 2 + 3 + 3 + 4 + x = 2 × 8
13 + x = 16
x = 3

答えは3です。たとえば順に A、B、C、D、E、F と名付け、辺を AE、BE、BF、CE、CF、CD、DE、DF とすれば、次数は順に 1、2、3、3、4、3 です。辺は8本で、出した数を接続に戻せます。

3. 次数の和から、

次数の和 = 4 + 2 + 2 + 1 + 1
         = 10
辺数 = 10 / 2
     = 5

答えは5本です。頂点を順に A、B、C、D、E とし、AB、AC、AD、AE、BC を置きます。A は4本、B と C は各2本、D と E は各1本に接します。辺も5本なので、求めた本数と元の条件の両方に合います。

4. 次数の和は 3 + 2 + 2 + 2 = 9 です。無向グラフの次数の和は辺数の2倍で偶数なので、9にはなりません。したがって存在しません。辺数を 9 / 2 本とすることもできません。

5. 次数の和は 4 + 4 + 1 + 1 + 0 = 10 で、偶数です。しかし、次数4の頂点は5頂点中の他の4頂点すべてに接する必要があります。次数0の頂点にも接することになり、孤立しているという条件と矛盾します。よって存在しません。和が偶数でも接続の条件を満たすとは限らない例です。

覚えておくこと

• 次数は、その頂点を端とする辺の本数です。
• 点のない交差は頂点に含めません。
• 次数の和は辺数の2倍で、必ず偶数です。
• 欠けた次数を求めたら、各辺の両端に戻して確認します。
• 和が偶数でも、指定された接続を作れるかは別に調べます。

どこで数え違えたかを見分ける

答案では、各頂点の横に書いた辺の名前と、辺の一覧に付けた印を見比べます。1本の辺に2個の印が付いていなければ、どちらの端を数え落としたか、または重ねて数えたかを追えます。交差の位置を頂点として書き込んでいる場合は、問題文にその指定があるかを確認します。

個別指導で確かめる箇所は、次数の和の式だけではありません。生徒が描いた図の点、辺の一覧、各頂点に接する辺の記録を並べ、1本ずつ対応させます。和が合っても異なる辺を入れ替えていることがあるため、各頂点の相手まで確認します。端を両側から数えた記録が、次数と辺数をつなぎます。