グラフの次数・握手補題・木・オイラー路
有限の無向グラフを辺の一覧で表し、次数の二重数え上げから木の辺数と一筆書きの条件へ進む。小さなグラフで、存在条件の確認と具体的な構成を区別する。
- 辺の一覧から各頂点の次数を計算し、握手補題で検算できる
- 奇次数の頂点が偶数個になる理由と、次数和だけでは存在を保証できない理由を説明できる
- 木と全域木を区別し、連結性の条件を付けて辺数の公式を使える
- オイラー路の存在を判定し、小グラフで通過順序を示せる
1. 点と線でつながりを表す
ここでいうグラフは関数の曲線ではなく、頂点集合 V と辺集合 E の組 G = (V, E) である。本記事は有限の無向単純グラフを扱う。無向とは辺に向きがないこと、単純とはループ（同じ頂点への辺）と多重辺（同じ2頂点を結ぶ複数の辺）がないことをいう。頂点数・辺数・次数は個数であり、長さなどの単位は付かない。
辺 ab は順序のない組 {a,b} を表し、ba と同じ辺である。a と b は隣接し、この辺は両頂点に接続するという。頂点 v に接続する辺の本数が次数 deg(v)。次数0の頂点は孤立点、次数1の頂点は葉と呼ぶ。図の線が交差しても、交点が頂点として指定されていなければ、そこで乗り換えることはできない。
V = {a,b,c,d,e}、E = {ab,bc,cd,da,bd,de} とする。このグラフ G の次数を求めよ。
解答・解説
a は ab,da の2本、b は ab,bc,bd の3本、c は bc,cd の2本、d は cd,da,bd,de の4本、e は de の1本に接続する。a,b,c,d,e の順に次数は (2,3,2,4,1)。奇次数の頂点は b,e、葉は e である。辺数は6。
| 頂点 | 接続する辺 | 次数 |
|---|---|---|
| a | ab, da | 2 |
| b | ab, bc, bd | 3 |
| c | bc, cd | 2 |
| d | cd, da, bd, de | 4 |
| e | de | 1 |
2. 握手補題と必要条件
証明では「頂点と、それに接続する辺の組」を数える。頂点 v を固定すれば deg(v) 組あるので、総数は次数の和。一方、辺を固定すれば端点が2つあるので2組、総数は辺数の2倍。この二重数え上げが握手補題である。例題1では 2+3+2+4+1 = 12 = 2×6 と検算できる。
奇次数の頂点を奇点という。次数の和が偶数なので、偶次数の寄与を除いた「奇数の和」も偶数になる。奇数を奇数個足すと奇数、偶数個足すと偶数だから、奇点は必ず偶数個である。ただし、これだけで指定された次数のグラフが存在するとは限らない。
4頂点の単純グラフに次数列 (3,3,1,1) は実現できるか。
解答・解説
実現できない。次数和は8で辺数4と整合し、奇点も4個で偶数、各次数も最大3以下である。しかし次数3の2頂点はそれぞれ他の全頂点に隣接するため、残り2頂点の次数は少なくとも2になり、次数1という指定に矛盾する。握手補題は必要条件であって十分条件ではない。
3. 連結性・閉路・木
辺に沿った移動で、頂点を繰り返さないものを単純パスと呼ぶ。任意の2頂点間にパスがあるグラフが連結である。閉路は、始点と終点が同じで、それ以外の頂点を繰り返さない巡回であり、単純グラフでは少なくとも3辺を使う。連結で閉路のないグラフを木という。1頂点・0辺も木に含める。
🔍 葉を取り除く帰納法
- 出発点
1頂点だけなら辺はなく公式が成り立つ。
- 葉の存在
最長の単純パスの端点を見る。パス外への辺があれば延長でき、パス内への別の辺があれば閉路ができる。どちらも不可能なので端点は葉である。
- 1頂点と1辺を除く
葉とその辺を除いても残りは連結で閉路がない木。帰納法を適用して、除いた1辺を戻す。
逆に、n頂点で連結かつ辺数 n−1 のグラフは木である。連結グラフから閉路上の辺を1本除いても連結は保たれるので、閉路を壊し続けると全頂点を含む木（全域木）が得られる。全域木だけで n−1 辺必要なため、元も n−1 辺なら余分な辺はなく、元自身が木である。閉路がなく連結とは限らないグラフは森。各成分が木なので、n頂点・c成分の森の辺数は n−c になる。
例題1の G の全域木を1つ作れ。さらに全部で何個あるか数えよ。
解答・解説
辺集合 {ab,bc,cd,de} は a→b→c→d→e というパスで、全5頂点を結ぶ4辺の木。どの全域木でも e を結ぶ de は必須である。残る4頂点では、対角線 bd を使わない場合、四角形 ab,bc,cd,da の4辺から1辺を除く4通り。bd を使う場合、a を ab または da の一方で、c を bc または cd の一方で結ぶので2×2=4通り。合計8個。
4. オイラー路：辺を一度ずつ通る
すべての辺をちょうど1回ずつ通る歩き方をオイラー路と呼ぶ。頂点の再訪は許される。始点と終点が一致するものをオイラー閉路、異なるものを開いたオイラー路と呼ぶ。本記事では辺が1本以上ある連結グラフについて判定する。辺があるのに連結でない場合は、孤立点を除いた部分が連結であることが必要になる。
| 奇点数（連結・1辺以上） | 存在するもの |
|---|---|
| 0個 | オイラー閉路 |
| 2個 | 開いたオイラー路。2奇点が始点と終点 |
| 4個以上 | オイラー路は存在しない |
必要性：途中の頂点では「入る辺」と「出る辺」が対になる。閉じた歩き方なら始点でも対になり、全次数が偶数。開いた歩き方では始点の出発と終点の到着だけが対にならず、その2頂点だけが奇数になる。奇点が偶数個であることと、一筆書き可能であることは同じではない。
十分性の考え方：全次数が偶数なら、未使用の辺をたどって進むと、出発点以外では入った辺に対する出口が残るため行き止まりにならず、出発点に戻る。未使用辺が残るときは連結性により、できた巡回上のどこかに未使用辺が接続する。そこから同様に巡回を作ってつなぎ込み、有限回で全辺を使う。奇点が2個なら、その2頂点を結ぶ仮の辺を1本加えて全次数を偶数にし、得た閉路から仮の辺を除けばよい。この証明中だけ多重辺を許しており、仮の辺は既存の辺と区別する。
例題1の G にオイラー路はあるか。あるなら順序を示せ。
解答・解説
G は連結で奇点は b,e の2個だから、b と e を両端とする開いたオイラー路がある。例えば b→a→d→c→b→d→e。通る辺は ab,da,cd,bc,bd,de の6本で、元の辺集合と一致し重複もない。b,d を再訪してもよい。閉路は奇点があるため存在しない。
次数列 (3,3,2,1,1) の単純グラフを1つ構成せよ。
解答・解説
V={a,b,c,d,e}, E={ab,ac,bc,ad,be} とすれば、順に次数は3,3,2,1,1。和は10で辺数5の2倍。構成によって存在を確かめたのであって、次数和だけを理由にしていない。
例題1の G から e と de を除く。残りにはオイラー閉路があるか。
解答・解説
ない。残りの次数は a,b,c,d の順に2,3,2,3で奇点は b,d。開いたオイラー路なら b→c→d→a→b→d があり、残る5辺を1回ずつ通る。
10頂点の木で、次数3の頂点が3個、次数2の頂点が2個、残りが葉のとき、葉の数を求め、構成を示せ。
解答・解説
葉は10−3−2=5個。次数和は3×3+2×2+5=18=2×9で整合。内部頂点のパス t1−s1−t2−s2−t3 を作り、t1に葉2個、t2に葉1個、t3に葉2個を付ける。これでt1,t2,t3の次数3、s1,s2の次数2を満たす10頂点9辺の木となる。
8頂点・3連結成分の森の辺数を求めよ。また「8頂点で5辺」だけで森と断定できるか。
解答・解説
森なら8−3=5辺。逆の断定はできない。三角形1個、独立な辺2本、孤立点1個なら頂点数3+4+1=8、辺数3+2=5だが三角形の閉路があり森ではない。
問1. 有限無向単純グラフの次数和が18なら辺数はいくつか。
問2. 6頂点5辺のグラフが木であると保証する追加条件はどれか。
問3. 1辺以上ある連結グラフの奇点が2個のとき正しいものはどれか。
問4. 単純グラフの次数列として実現できないものはどれか。
まとめ：次数は辺の端点を数える量で、総和は辺数の2倍。奇点は偶数個だが、その条件だけでグラフの存在は決まらない。連結グラフでは木と「辺数 n−1」が同値。オイラー路では頂点でなく辺を1回ずつ使い、連結性と奇点数0または2が決め手になる。これらは本記事中の二重数え上げ・帰納法・巡回のつなぎ込みを根拠とする、有限グラフについての厳密な主張である。