§D2.7グラフ・木・連結性・オイラー路

最終更新

頂点とそれらを結ぶ辺だけからなる構造は、道路網のように対象どうしのつながりを表す場面に幅広く現れます。こうした構造でしばしば問題になるのは、各頂点がいくつの相手と隣接しているかという局所的な情報から、全体がひとつにつながっているか、迂回のない形をしているか、すべてのつながりを一筆書きでたどることができるかといった大域的な性質がどこまで決まるかです。この局所と大域の関係を扱う対象がグラフであり、次数、連結性、木、オイラー回路がその基本的な道具となります。グラフは、これまで数え上げを通じて調べてきた有限の対象と同じ枠組みに属する題材であり、以降の学習でも基礎として繰り返し参照されます。本記事では、次数や連結性に関する基本的な性質、および木とオイラー回路について解説します。

1 グラフと次数

定義 1.1 (単純無向グラフ・隣接・次数). （単純無向）グラフ (graph) とは、対G=(V,E)G=(V,E)であって、VVが空でない有限集合、EEがVVの相異なる2元からなる部分集合の集合であるものをいう。VVの元を頂点 (vertex)、EEの元を辺 (edge) とよび、∣V∣|V|を位数 (order)、∣E∣|E|を辺数 (size)（サイズ）という。辺e={u,v}e=\{u,v\}をuvuvとも書き、このときuuとvvは隣接する (adjacent) といい、u,vu,vはeeの端点 (endpoint)、eeはu,vu,vに接続する (incident) という。頂点vvに接続する辺の本数

deg⁡(v)=∣{ e∈E:v∈e }∣\deg(v) = |\{\, e\in E : v\in e \,\}|

をvvの次数 (degree) という。次数の最大値をΔ(G)\Delta(G)、最小値をδ(G)\delta(G)と書く。次数00の頂点を孤立点 (isolated vertex) という。

この定義では、同じ2頂点を結ぶ辺は高々1本であり（多重辺 (multiple edge) を許さない）、両端点が一致する辺（ループ (loop)）も許さない。両端点を結ぶ辺を複数許す構造を多重グラフ (multigraph)、辺に向きを付けE⊆V×VE\subseteq V\times Vとする構造を有向グラフ (directed graph) という。以下、断りなくグラフといえば単純無向グラフを指す。

握手補題は、局所量である次数の総和が大域量である辺数で表せることを述べる、最初の基本定理です。

定理 1.2 (握手補題). 任意のグラフG=(V,E)G=(V,E)に対し

∑v∈Vdeg⁡(v)=2 ∣E∣.\sum_{v\in V}\deg(v) = 2\,|E|.

証明. 接続する頂点と辺の対の集合

I={ (v,e)∈V×E:v∈e }I = \{\, (v,e)\in V\times E : v\in e \,\}

の要素の個数を二通りに数える。まず各頂点vvを固定すると、(v,e)∈I(v,e)\in Iとなるeeの個数はちょうどdeg⁡(v)\deg(v)である（次数の定義）。ゆえに∣I∣=∑v∈Vdeg⁡(v)|I| = \sum_{v\in V}\deg(v)。次に各辺eeを固定すると、eeはちょうど2個の端点をもつから（単純グラフではループがなく端点は相異なる2頂点）、(v,e)∈I(v,e)\in Iとなるvvの個数はちょうど22である。ゆえに∣I∣=∑e∈E2=2 ∣E∣|I| = \sum_{e\in E}2 = 2\,|E|。同一の集合IIを数えた二つの式を等号で結んで結論を得る。▨

系 1.3. 任意のグラフにおいて、奇数の次数をもつ頂点の個数は偶数である。

証明. 頂点集合を次数の偶奇で分け、Veven={v:deg⁡(v) 偶}V_{\mathrm{even}}=\{v:\deg(v)\ \text{偶}\}、Vodd={v:deg⁡(v) 奇}V_{\mathrm{odd}}=\{v:\deg(v)\ \text{奇}\}とおく。定理 1.2より

∑v∈Vevendeg⁡(v)+∑v∈Vodddeg⁡(v)=2 ∣E∣\sum_{v\in V_{\mathrm{even}}}\deg(v) + \sum_{v\in V_{\mathrm{odd}}}\deg(v) = 2\,|E|

であり、右辺は偶数である。左辺第1項は偶数の和だから偶数である。したがって左辺第2項∑v∈Vodddeg⁡(v)\sum_{v\in V_{\mathrm{odd}}}\deg(v)も偶数でなければならない。これは奇数を∣Vodd∣|V_{\mathrm{odd}}|個加えた和であり、奇数の和が偶数になるのは加える個数が偶数のとき、かつそのときに限る。ゆえに∣Vodd∣|V_{\mathrm{odd}}|は偶数である。▨

2 歩道・道・連結性

定義 2.1 (歩道・小道・道・閉路・部分グラフ). グラフG=(V,E)G=(V,E)において、頂点と辺の交互列

W:v0, e1, v1, e2, …, ek, vk(ei={vi−1,vi}∈E)W: v_0,\, e_1,\, v_1,\, e_2,\, \dots,\, e_k,\, v_k \qquad(e_i=\{v_{i-1},v_i\}\in E)

を、v0v_0からvkv_kへの長さkkの歩道 (walk) という。単純グラフでは辺は端点で決まるので、歩道を頂点列v0v1⋯vkv_0v_1\cdots v_kで表してよい。歩道が

  • 相異なる辺のみを用いるとき小道 (trail)、
  • 相異なる頂点のみを用いるとき道 (path)（このとき辺も自動的に相異なる）

という。v0=vkv_0=v_kの歩道を閉じた歩道 (closed walk) という。長さk≥3k\ge 3の閉じた歩道でv0,…,vk−1v_0,\dots,v_{k-1}が相異なるものを閉路 (cycle) という（単純グラフではループ・多重辺がないため閉路の長さは33以上）。

グラフG′=(V′,E′)G'=(V',E')がG=(V,E)G=(V,E)の部分グラフ (subgraph) であるとは、V′⊆VV'\subseteq VかつE′⊆EE'\subseteq Eで、E′E'の各辺の端点がV′V'に属することをいう。

道と歩道は、始終点が同じであれば一方が存在すれば他方も存在します。次はその基本事実であり、連結性の議論で繰り返し使います。

補題 2.2.uuからvvへの歩道が存在すれば、uuからvvへの道が存在する。

証明.uuからvvへの歩道は少なくとも一つ存在するから、その中で長さが最小のものをW:v0=u,…,vk=vW: v_0=u,\dots,v_k=vとする（長さは非負整数で下に有界だから最小値をとる歩道が存在する）。もしWWが同じ頂点を二度通れば、vi=vjv_i=v_j（i<ji<j）となる添字があり、部分列vi+1,…,vjv_{i+1},\dots,v_jを取り除いた

v0,…,vi,vj+1,…,vkv_0,\dots,v_i,v_{j+1},\dots,v_k

は再びuuからvvへの歩道であって長さがj−i≥1j-i\ge 1だけ短い。これはWWの最小性に反する。ゆえにWWは相異なる頂点のみを通り、道である。▨

定義 2.3 (連結性・連結成分・到達可能性). グラフG=(V,E)G=(V,E)の頂点u,vu,vについて、uuからvvへの歩道が存在するとき、vvはuuから到達可能 (reachable) であるといいu∼vu\sim vと書く。GGの任意の2頂点が互いに到達可能であるとき、GGは連結 (connected) であるという。到達可能性関係∼\simの各同値類CCについて、CCの頂点と両端点がCCに属する辺からなる部分グラフをGGの連結成分 (connected component) という。

命題 2.4. 到達可能性∼\simはVV上の同値関係であり、GGの各連結成分は連結なグラフである。特にGGは連結であることと、∼\simの同値類がただ一つであることが同値である。

証明.∼\simが§D2.5 定義 2.1の3条件を満たすことを示す。反射律：各vvに対し長さ00の歩道vvがvvからvvへの歩道を与えるのでv∼vv\sim v。対称律：u∼vu\sim vとし歩道v0=u,…,vk=vv_0=u,\dots,v_k=vをとると、辺は無向だから逆順の列vk,…,v0v_k,\dots,v_0も歩道でありv∼uv\sim u。推移律：u∼vu\sim v、v∼wv\sim wとし、uuからvvへの歩道とvvからwwへの歩道をとってvvで連結するとuuからwwへの歩道を得るのでu∼wu\sim w。

以上より∼\simは同値関係である。CCを∼\simの同値類とし、x,y∈Cx,y\in Cをとる。x∼yx\sim yであるから、xxからyyへの歩道WWが存在する。WW上の各頂点zzは、WWのxxからzzまでの部分歩道によりx∼zx\sim zを満たすのでCCに属する。したがってWWのすべての頂点と辺はCCが定める連結成分に属し、この連結成分は連結である。GGが連結であることは全頂点が互いに到達可能、すなわち∼\simの同値類がただ一つであることと同値である。▨

同値関係と分割の一対一対応（§D2.5 命題 2.5）により、頂点集合は連結成分へと過不足なく分割されます。

3 木と全域木

定義 3.1 (木・森). 連結かつ閉路をもたないグラフを木 (tree) という。閉路をもたない（連結とは限らない）グラフを森 (forest) という。森の各連結成分は命題 2.4により連結であり、森の部分グラフとして閉路をもたないから木である。

木の構造を引き出す出発点は、端に必ず次数11の頂点（葉）があることです。

補題 3.2. 少なくとも2頂点をもつ木は、次数11の頂点（葉）を少なくとも2つもつ。

証明.TTをn≥2n\ge 2頂点の木とする。TTは連結で頂点が2個以上あるから辺を少なくとも1本もち、長さ11以上の道が存在する。TTの道のうち長さ最大のものを一つとりP:v0,v1,…,vkP: v_0,v_1,\dots,v_k（k≥1k\ge 1）とする（道の長さは頂点数未満で上に有界だから最大値をとる道が存在する）。両端v0,vkv_0,v_kがともに葉であることを示す。

v0v_0が次数22以上と仮定する。PP上でのv0v_0の隣はv1v_1のみだから、v0v_0にはv1v_1と異なる隣接頂点wwが存在する。

  • wwがPP上にないとき、w,v0,v1,…,vkw,v_0,v_1,\dots,v_kは道であって長さk+1k+1をもち、PPの最大性に反する。
  • wwがPP上にあるとき、w=viw=v_i（i≥2i\ge 2、v1v_1とは仮定より異なる）であり、v0,v1,…,vi,v0v_0,v_1,\dots,v_i,v_0は長さi+1≥3i+1\ge 3の閉路となって、TTが閉路をもたないことに反する。

いずれも矛盾だからdeg⁡(v0)=1\deg(v_0)=1。vkv_kについても同様にdeg⁡(vk)=1\deg(v_k)=1。道PPの両端は相異なるからv0≠vkv_0\ne v_k、ゆえに葉が少なくとも2つある。▨

木の特徴づけの証明は、連結グラフの辺数についての下からの評価を繰り返し用います。先にこれを独立した補題として示します。

補題 3.3.HHを連結グラフとし、vvをdeg⁡(v)=1\deg(v)=1を満たす頂点とする。HHからvvとvvに接続する辺を除いて得られる部分グラフH−vH-vは連結である。

証明.H−vH-vの任意の2頂点x,yx,yをとる。HHは連結であるから、xxからyyへの道PPが存在する。PPがvvを通るならば、x,y≠vx,y\ne vであるからvvはPPの内部頂点であり、PPはvvに接続する相異なる2辺を用いる。これはdeg⁡(v)=1\deg(v)=1に反する。したがってPPはvvを通らず、H−vH-vに含まれる。ゆえにH−vH-vは連結である。▨

補題 3.4.HHを連結グラフとし、eeをHHの閉路に属する辺とする。HHからeeだけを除いて得られる部分グラフH−eH-eは連結である。

証明.H−eH-eの任意の2頂点u,vu,vをとる。HHは連結であるから、uuからvvへの道PPが存在する。PPがeeを用いなければ、PPはH−eH-eに含まれる。PPがe={x,y}e=\{x,y\}を用いるならば、eeを含む閉路からeeを除いて得られるxxからyyへの道で、PPの辺eeを置き換える。これによりH−eH-eに含まれるuuからvvへの歩道を得るので、補題 2.2によりH−eH-eに含まれるuuからvvへの道が存在する。ゆえにH−eH-eは連結である。▨

補題 3.5.nn頂点の連結グラフの辺数はn−1n-1以上である。

証明. 頂点数nnについての帰納法による。n=1n=1なら辺数≥0=n−1\ge 0 = n-1。n≥2n\ge 2の連結グラフHHをとる。連結で頂点が2個以上あるから孤立点はなくδ(H)≥1\delta(H)\ge 1。

  • ある頂点vvがdeg⁡(v)=1\deg(v)=1をもつなら、vvとその唯一の辺を除いたH−vH-vを考える。補題 3.3によりH−vH-vはn−1n-1頂点の連結グラフである。帰納法の仮定よりH−vH-vはn−2n-2本以上の辺をもち、HHはそれにvvの1辺を加えてn−1n-1本以上。
  • すべての頂点がdeg⁡≥2\deg\ge 2なら、定理 1.2より2∣E∣=∑vdeg⁡(v)≥2n2|E| = \sum_v\deg(v)\ge 2n、すなわち∣E∣≥n≥n−1|E|\ge n\ge n-1。

いずれの場合も∣E∣≥n−1|E|\ge n-1。▨

定理 3.6.nn頂点のグラフGGについて、次の4条件は同値である。

  1. GGは木である（連結かつ閉路をもたない）。
  2. GGは連結で、辺数はn−1n-1である。
  3. GGは閉路をもたず、辺数はn−1n-1である。
  4. GGの任意の2頂点は、ちょうど一つの道で結ばれる。

証明.(1)⇒\Rightarrow(2)を示す。GGが木なら連結である。辺数がn−1n-1であることをnnに関する§A3.10 定理 1.1で示す。n=1n=1のとき木は辺をもたず0=n−10=n-1。n≥2n\ge 2のとき、補題 3.2より葉vvが存在する。補題 3.3によりG−vG-vは連結であり、閉路のないGGの部分グラフだから閉路をもたない。したがってG−vG-vは木である。帰納法の仮定よりG−vG-vは(n−1)−1=n−2(n-1)-1=n-2本の辺をもち、vvの1辺を戻してGGはn−1n-1本。

(2)⇒\Rightarrow(3)を示す。GGが連結で辺数n−1n-1とする。閉路をもたないことを背理法で示す。GGが閉路CCをもつと仮定し、CCの辺eeを1本除く。補題 3.4によりG−eG-eは連結である。G−eG-eはnn頂点・n−2n-2辺の連結グラフとなり、補題 3.5に反する。ゆえにGGは閉路をもたない。

(3)⇒\Rightarrow(1)を示す。GGが閉路をもたず辺数n−1n-1とする。連結であることを示せば木である。GGの連結成分をG1,…,GcG_1,\dots,G_cとし、GiG_iの頂点数をnin_iとすると∑ini=n\sum_i n_i = n。各GiG_iは命題 2.4により連結であり、GGの部分グラフとして閉路をもたないから木である。既に示した(1)⇒\Rightarrow(2)を各GiG_iに適用すると辺数はni−1n_i-1。ゆえに

n−1=∣E∣=∑i=1c(ni−1)=n−c,n-1 = |E| = \sum_{i=1}^{c}(n_i-1) = n - c,

したがってc=1c=1、すなわちGGは連結で木である。

(1)⇒\Rightarrow(4)を示す。GGが木なら連結だから、任意の2頂点u,vu,vは少なくとも一つの道で結ばれる（補題 2.2）。相異なる2つの道P,QP,Qがあると仮定して矛盾を導く。両者はuuを共有するので、uuから出発してPPとQQが一致する最長の初期部分の最後の頂点をaaとする。P≠QP\ne Qであり両道の終点はともにvvであるからa≠va\ne vであり、aaの直後でPPとQQが用いる辺は相異なる。aaより後でPPとQQが最初に共有する頂点をbbとする。両道は遅くともvvで共有するので、このようなbbが存在する。aaからbbまでのPPの部分道とQQの部分道は、両端a,ba,b以外に共有点をもたず、aaの直後で異なる辺を用いるから相異なる。両部分道がともに長さ11ならば、いずれも辺ababとなって相異性に反するので、両部分道をつないで得る閉じた歩道の長さは33以上である。その内部頂点は相異なるから、この閉じた歩道は閉路である。これはGGが木で閉路をもたないことに反する。ゆえに道は一意である。

(4)⇒\Rightarrow(1)を示す。任意の2頂点がちょうど一つの道で結ばれるとする。特に道が存在するので連結である。閉路v0,…,vk−1,v0v_0,\dots,v_{k-1},v_0（k≥3k\ge 3）があれば、v0v_0とv1v_1は辺v0v1v_0v_1による道と、v0,vk−1,…,v1v_0,v_{k-1},\dots,v_1という道の、相異なる2つの道で結ばれ、一意性に反する。ゆえに閉路をもたず、GGは木である。▨

例 3.7 (木の特徴づけにおける二条件の必要性). 互いに頂点を共有しない三角形と孤立点からなるグラフをG1G_1とする。G1G_1は44頂点と3=4−13=4-1本の辺をもつが、連結でなく、三角形を閉路として含むので木ではない。したがって、辺数がn−1n-1であることだけでは木であると結論することができない。一方、三角形G2G_2は連結であるが、33頂点と3>3−13>3-1本の辺をもち、閉路を含むので木ではない。したがって、連結性だけでも木であると結論することができない。

定義 3.8 (全域木). グラフG=(V,E)G=(V,E)に対し、GGの部分グラフT=(V,ET)T=(V,E_T)が木であるとき、TTをGGの全域木 (spanning tree) という。

命題 3.9. 任意の連結グラフG=(V,E)G=(V,E)は全域木をもつ。

証明.VVを頂点集合とするGGの連結な部分グラフ全体を考える。GG自身がその一つだから空でなく、辺数は非負整数で下に有界だから、辺数が最小の連結全域部分グラフTTが存在する。TTが木であること、すなわち閉路をもたないことを示す。TTが閉路CCをもつと仮定し、CCの辺eeを1本除く。補題 3.4により、TTからeeだけを除いて得られる部分グラフはなお連結で、VVを頂点集合にもつ。これはTTより辺数が1少ない連結全域部分グラフとなり、TTの最小性に反する。ゆえにTTは閉路をもたず、連結だから全域木である。▨

例 3.10 (閉路グラフの全域木). 頂点集合を{1,2,3,4}\{1,2,3,4\}、辺集合を{12,23,34,41}\{12,23,34,41\}とする閉路グラフを考える。辺4141を除いた部分グラフは、すべての頂点を含む道1,2,3,41,2,3,4であり、連結かつ閉路をもたない。したがって、この部分グラフはもとのグラフの全域木である。同様に、四つの辺のいずれを一つ除いても全域木を得る。

4 オイラー回路

定義 4.1 (オイラー小道・オイラー回路). グラフGGのオイラー小道 (Euler trail) とは、GGのすべての辺をちょうど一度ずつ通る小道をいう。始終点が一致するオイラー小道をオイラー回路 (Euler circuit)、一致しないものを開いたオイラー小道 (open Euler trail) という。

オイラー回路の存在は、次数の偶奇という純粋に局所的な条件で完全に判定することができます。ここが、後述のハミルトン路と決定的に異なる点です。

定理 4.2 (オイラーの定理). 少なくとも1本の辺をもつ連結グラフGGについて、次が成り立つ。

  1. GGがオイラー回路をもつのは、すべての頂点の次数が偶数であるとき、かつそのときに限る。
  2. GGが開いたオイラー小道をもつのは、奇数の次数をもつ頂点がちょうど2個であるとき、かつそのときに限る。

証明.(1)を示す。必要性を示す。GGがオイラー回路W:v0,e1,…,em,vm (v0=vm)W: v_0,e_1,\dots,e_m,v_m\ (v_0=v_m)をもつとする。各頂点vvについて、WWがvvを通過するたびにvvに入る辺と出る辺の2本を使う。WWは閉じており、各辺をちょうど一度ずつ用いるから、vvに接続するすべての辺はWWにおける「通過」に2本ずつ組になって現れる。ゆえにdeg⁡(v)\deg(v)は偶数である（始点v0=vmv_0=v_mについても、出発の1本と帰着の1本が組になり偶数）。

十分性を示す。すべての頂点が偶数次数の連結グラフGG（辺数≥1\ge 1）を考える。GGの閉じた小道のうち長さ（辺数）が最大のものをWWとする（閉じた小道は少なくとも一つ存在する：偶数次数で辺があるのでδ≥2\delta\ge 2の非自明成分をたどれば閉路がとれ、閉路は閉じた小道である。長さは辺数で上に有界だから最大値をとる）。WWがすべての辺を用いることを示す。

WWが用いない辺があると仮定する。WW上に現れる頂点の集合をV(W)V(W)とおく。このとき、WWが用いない辺でV(W)V(W)の頂点に接続するものが存在する。実際、V(W)≠VV(W)\ne VならGGの連結性よりV(W)V(W)とその補集合をまたぐ辺があり、その辺はV(W)V(W)外に端点をもつのでWWには現れず、V(W)V(W)の頂点xxに接続する。V(W)=VV(W)=Vの場合、用いない辺はすべて端点がV(W)V(W)にあり、やはりV(W)V(W)の頂点に接続する。いずれの場合も、WWが用いずx∈V(W)x\in V(W)に接続する辺が存在する。

WWの辺をすべて除いた部分グラフG′G'を考える。WWは閉じた小道だから、各頂点でWWが用いる辺の本数は偶数である（各通過で2本）。ゆえにG′G'における各頂点の次数は（もとの偶数から偶数を引いて）偶数である。xxはG′G'で辺eeをもつのでG′G'における次数は22以上の偶数である。

xxからG′G'の中で小道を伸ばす。xxを出て、まだ用いていない辺を選んで進む。xx以外の頂点yyに入るたび、yyのG′G'における次数は偶数であり、yyに入るまでに用いたyyの辺は奇数本になるから、まだ用いていないyyの辺が必ず残り、進み続けられる。有限グラフゆえこの過程は止まり、止まれる頂点は入ったきり出られない頂点、すなわちxxに限る。こうしてG′G'の中にxxを始終点とする閉じた小道W′W'（長さ≥1\ge 1）を得る。WWとW′W'は辺を共有せず、ともにxxを通るから、xxでW′W'を挿入して一つの閉じた小道につなげられ、その長さはWWより真に大きい。これはWWの最大性に反する。ゆえにWWはすべての辺を用い、オイラー回路である。

(2)を示す。必要性を示す。開いたオイラー小道WWが始点ss、終点t (≠s)t\ (\ne s)をもつとする。中間で通過する頂点では上と同様に辺が2本ずつ組になり偶数次数、始点ssでは最初の出発の1本が余って奇数次数、終点ttでは最後の帰着の1本が余って奇数次数となる。ゆえに奇数次数の頂点はちょうどs,ts,tの2個である。

十分性を示す。奇数次数の頂点がちょうど2個u,vu,vであるとする。GGに新しい頂点wwを1個加え、辺wu,wvwu,wvを追加したグラフをG^\hat Gとする。wwの次数は22（偶数）、u,vu,vは次数が1増えて偶数になり、他は不変で偶数のまま、G^\hat Gは連結である。(1)の十分性よりG^\hat Gはオイラー回路W^\hat Wをもつ。W^\hat Wから辺wu,wvwu,wvと頂点wwを取り除くと、wwで切れてuuからvvへ至る小道が残り、これはGGのすべての辺をちょうど一度ずつ通る開いたオイラー小道である。▨

例 4.3 (ケーニヒスベルクの橋). ケーニヒスベルクの七つの橋を四つの陸地を頂点、橋を辺として表すと、同じ二つの陸地を結ぶ橋が複数あるため、得られる構造は本記事の定義する単純グラフではなく多重グラフである。四つの陸地に接続する橋の本数はそれぞれ3,3,3,53,3,3,5である。各橋をちょうど一度通る歩き方では、中間の陸地に入る橋と出る橋が対になるので、中間の陸地に接続する橋の本数は偶数でなければならない。始点と終点が異なる場合でも奇数本の橋が接続する陸地はその二つだけである。実際には四つの陸地がすべて奇数本の橋をもつので、七つの橋をちょうど一度ずつ通る歩き方は存在しない。この偶奇の必要性は多重辺を区別して数えても成り立つが、定理 4.2の主張自体は単純グラフを対象としている。

例 4.4 (連結性を外した反例). 互いに頂点を共有しない二つの三角形からなるグラフを考える。すべての頂点の次数は22であるが、一方の三角形の辺から他方の三角形の辺へ歩道で移ることができない。したがって、このグラフはすべての辺を通る一つのオイラー回路をもたない。これは定理 4.2から連結性の仮定を外すことができないことを示す。

例 4.5 (K5K_5上のオイラー回路（検算つき）).55頂点1,2,3,4,51,2,3,4,5の完全グラフK5K_5（任意の2頂点が隣接）を考える。各頂点は他の44頂点と隣接するのでdeg⁡(v)=4\deg(v)=4、辺数は∣E∣=(52)=10|E|=\binom{5}{2}=10。握手補題の検算：∑vdeg⁡(v)=5×4=20=2×10=2∣E∣\sum_v\deg(v)=5\times 4=20=2\times 10=2|E|が成り立つ。全頂点が偶数次数だから定理 4.2によりオイラー回路が存在する。実際、

1→2→3→4→5→1→3→5→2→4→11\to 2\to 3\to 4\to 5\to 1\to 3\to 5\to 2\to 4\to 1

を検算する。用いる辺を順に並べると

12, 23, 34, 45, 15, 13, 35, 25, 24, 1412,\ 23,\ 34,\ 45,\ 15,\ 13,\ 35,\ 25,\ 24,\ 14

の1010本で、これはK5K_5の全辺{12,13,14,15,23,24,25,34,35,45}\{12,13,14,15,23,24,25,34,35,45\}をちょうど1本ずつ含み、重複がない。始点と終点はともに11。したがってこれはオイラー回路である。

5 二部性とハミルトン路

二部性の証明は、閉じた歩道から閉路を取り出す議論を用います。先にこれを独立した補題として示します。

定義 5.1 (二部グラフ・二部分割). グラフG=(V,E)G=(V,E)が二部グラフ (bipartite graph) であるとは、空集合であることも許す部分集合A,B⊆VA,B\subseteq Vで、V=A⊔BV=A\sqcup Bを満たし、すべての辺がAAの頂点とBBの頂点を結ぶものが存在することをいう。このとき、V=A⊔BV=A\sqcup BをGGの二部分割 (bipartition) という。

補題 5.2. グラフGGが奇数長の閉じた歩道をもつならば、GGは奇数長の閉路をもつ。

証明. 閉じた歩道の長さに関する帰納法による。C:v0,v1,…,vk=v0C: v_0,v_1,\dots,v_k=v_0をGGの奇数長kkの閉じた歩道とする。CCが始終点以外に重複頂点をもたなければ、CC自身が閉路であり長さは奇数である（長さ11は単純グラフではループがなく起こらないので長さ≥3\ge 3）。重複頂点xx（x=vi=vjx=v_i=v_j、0≤i<j≤k0\le i<j\le kで始終点の一致{i,j}={0,k}\{i,j\}=\{0,k\}以外の重複）があれば、CCをxxで2つの閉じた歩道vi,…,vjv_i,\dots,v_jとvj,…,vk,v1,…,viv_j,\dots,v_k,v_1,\dots,v_iに分ける。両者の長さの和はCCの奇数長kkに等しいから、少なくとも一方は奇数長であり、それはCCより短い。帰納法の仮定よりその中に奇数長の閉路がある。GGはその閉路をもつ。▨

定理 5.3. グラフGGが二部グラフであるのは、GGが奇数長の閉路をもたないとき、かつそのときに限る。

証明. 必要性.GGがA,BA,Bへの二部分割をもつとし、閉路v0,v1,…,vk−1,v0v_0,v_1,\dots,v_{k-1},v_0（k≥3k\ge 3）をとる。各辺はAAとBBを結ぶから、閉路を進むたびに属する側がA,BA,Bと交互に入れ替わる。v0∈Av_0\in Aとするとvi∈Av_i\in Aであることとiiが偶数であることが同値になる。閉路はvk=v0∈Av_k=v_0\in Aで閉じるからkkは偶数であり、閉路の長さは偶数である。ゆえに奇数長の閉路はもたない。

十分性.GGが奇数長の閉路をもたないとする。まず、二部分割は各連結成分ごとに構成して合併すればよいので、GGは連結としてよい。頂点rrを一つ固定し、d(v)d(v)をrrからvvへの最短の道の長さ（rrからvvへの歩道の最小長さ、連結性より有限）とする。

A={v:d(v) 偶},B={v:d(v) 奇}A=\{v: d(v)\ \text{偶}\},\qquad B=\{v: d(v)\ \text{奇}\}

とおく。これが求める分割、すなわちすべての辺がAAとBBを結ぶことを示す。

まず、辺uv∈Euv\in Eに対し∣d(u)−d(v)∣≤1|d(u)-d(v)|\le 1である（rrからuuへの最短道に辺uvuvを継ぐとrrからvvへの長さd(u)+1d(u)+1の歩道ができd(v)≤d(u)+1d(v)\le d(u)+1、対称にd(u)≤d(v)+1d(u)\le d(v)+1）。

いま辺uvuvの両端が同じ側にあると仮定するとd(u)d(u)とd(v)d(v)は同じ偶奇をもち、∣d(u)−d(v)∣≤1|d(u)-d(v)|\le 1と合わせてd(u)=d(v)d(u)=d(v)を得る。rrからuuへの最短道PP（長さd(u)d(u)）、rrからvvへの最短道QQ（長さd(v)d(v)）をとり、PP、辺uvuv、QQの逆順、を継ぐとrrを始終点とする長さ

d(u)+1+d(v)=2d(u)+1d(u)+1+d(v)=2d(u)+1

の閉じた歩道CCができ、これは奇数長である。補題 5.2よりGGは奇数長の閉路をもち、仮定に反する。ゆえに辺uvuvの両端が同じ側にあることはなく、すべての辺はAAとBBを結ぶ。GGは二部グラフである。▨

例 5.4 (二部グラフと非二部グラフ). 三つの頂点からなる集合AAと三つの頂点からなる集合BBをとり、AAの各頂点とBBの各頂点を辺で結び、同じ集合に属する二頂点は辺で結ばない。この完全二部グラフK3,3K_{3,3}ではV=A⊔BV=A\sqcup Bが二部分割である。偶数2m≥42m\ge 4に対する長さ2m2mの閉路も、頂点を閉路に沿って交互に二つの集合へ入れることで二部分割を得る。さらに、頂点集合を{0,…,m}×{0,…,n}\{0,\dots,m\}\times\{0,\dots,n\}とし、一方の座標だけが11異なる頂点を辺で結ぶ有限格子グラフは、座標の和の偶奇によって二部分割を得る。一方、三角形は奇数長の閉路そのものであるから、定理 5.3により二部グラフではない。

注意 5.5 (ハミルトン路には簡明な判定条件がない).GGのハミルトン路とはすべての頂点をちょうど一度ずつ通る道、ハミルトン閉路とはすべての頂点をちょうど一度ずつ通る閉路をいう。名称の類似にもかかわらず、オイラー小道（辺をすべて通る）とハミルトン路（頂点をすべて通る）は性質が大きく異なる。定理 4.2のように次数の偶奇だけで判定できる必要十分条件は、ハミルトン路・閉路には得られない。たとえば同じ次数列をもつグラフでもハミルトン閉路の有無は異なりうるため、次数だけでは判定できない。ハミルトン閉路を判定する手続きと計算量は、後続の計算量理論へ委ねる。

6 演習

問題 6.1 (木の二部性). 任意の木が二部グラフであることを証明せよ。

解答.

木TTの頂点rrを一つ固定し、各頂点vvに対してd(v)d(v)をrrからvvへの一意な道の長さとする。この道は定理 3.6 (4)により存在して一意に定まる。A={v:d(v) は偶数}A=\{v:d(v)\text{ は偶数}\}、B={v:d(v) は奇数}B=\{v:d(v)\text{ は奇数}\}とおく。

辺uvuvをとり、rrからuuへの一意な道をPPとする。vvがPP上にある場合、vvからuuまでのPPの部分道と辺uvuvが閉路を作らないためには、vvがPP上でuuの直前の頂点でなければならず、d(u)=d(v)+1d(u)=d(v)+1である。vvがPP上にない場合、PPに辺uvuvを継いだ頂点列はrrからvvへの道であり、道の一意性からこの道の長さがd(v)d(v)に等しいのでd(v)=d(u)+1d(v)=d(u)+1である。いずれの場合もd(u)d(u)とd(v)d(v)の偶奇は異なる。したがって、すべての辺はAAとBBを結び、TTは二部グラフである。▨

問題 6.2 (K4K_4から一辺を除いたグラフ). 頂点集合を{1,2,3,4}\{1,2,3,4\}とする完全グラフK4K_4から辺1212を除いたグラフについて、奇数次数の頂点を求め、開いたオイラー小道を一つ構成せよ。

解答.

頂点1,21,2の次数は22であり、頂点3,43,4の次数は33である。したがって、奇数次数の頂点は3,43,4である。頂点列

3,1,4,2,3,43,1,4,2,3,4

が用いる辺は順に13,14,24,23,3413,14,24,23,34であり、これらはグラフの全辺をちょうど一度ずつ尽くす。始点と終点は相異なるので、この頂点列は開いたオイラー小道である。▨

問題 6.3 (閉路グラフの全域木).m≥3m\ge 3とし、頂点集合{v1,…,vm}\{v_1,\dots,v_m\}と辺集合{v1v2,v2v3,…,vm−1vm,vmv1}\{v_1v_2,v_2v_3,\dots,v_{m-1}v_m,v_mv_1\}をもつ閉路グラフを考える。このグラフの全域木の個数を求め、その答えを証明せよ。

解答.

閉路の辺を一つ除くと、すべての頂点を含む道が残るので全域木を得る。除く辺の選び方はmm通りあり、異なる辺を除けば異なる全域木を得る。

逆に、この閉路グラフの全域木TTはmm頂点の木であるから、定理 3.6 (2)によりm−1m-1本の辺をもつ。もとのグラフの辺数はmmであり、TTはその部分グラフであるから、TTはもとの辺をちょうど一つ除いて得られる。したがって、全域木の個数はmmである。▨

前提記事