０． は じ め に 　１． 基 本 事 項 　２． サ イ ク ル 、 森 、 カ ッ ト 　３． 基 本 サ イ ク ル 、 極 大 サ イ ク ル 　４． 正 則 性 　５． 集 合 空 間 　６． プ リ ズ ム 　７． 分 割 　８． フ ロ ー 　９． 連 結 性 １０． 平 面 性 １１． サ イ ク ル に よ る 被 覆 １２． マ ト ロ イ ド １３． 集 合 族 １４． 附 録 （ 一筆書き , Grinberg の定理 , トーナメント , Cayley の定理 , Hajos の合併 , 染色多項式 , Tutte 多項式 , Kuratowski の定理の証明 , Pfaffian 向き付け ） 参 考 書　　　演 習 略 解　　　　　　更新履歴 〒 感想やご意見

グラフ理論における「グラフ」というのはいくつかの点をいくつかの線でつないだモノである。

普通はどの点とどの点が結ばれてるかのみに着目しどのように結ばれているかは問わないことが多いが、幾何学的グラフ理論では点集合としての（位相的）図形として結ばれ方も重視する。

この２つの見方　― 「システム」としての見方と「図形」としての見方 ―　が可能なことからグラフは一見単純ではあるが奥深い数学的な対象となっている。

グラフ理論は身近に存在する。
たとえば我々はいたるところで「植木算」のお世話になっているが、植木算の中にグラフ理論の主要な考えの発端が見られる。

この講義ではグラフ理論の応用数学的な側面よりも純粋数学的な側面に焦点を絞った。
形式的な記述でわかりにくい部分も図を見ればわかってしまうことが多いように図をたくさん入れておいた。

予備知識はほとんど不要であるが、ベクトル空間やポセット（半順序集合）についてある程度親しんでいることが期待される。（ 初歩的な点集合論の用語（内部、外部、境界、閉包など）を使うところもある. ）最初の通読に際しては４章、５章、６章、１２章、１３章は跳ばすというのもいいと思う。

なお、いくつかの章末に精選した演習問題を配した。略解もあるので利用されたい。

グラフを厳密に定義することから始める。

一般に、互いに素（ = 交わらない ）な有限集合 V ，E と写像 μ：E → P(V) に対してペア Γ = (V, E) = (V, E; μ) は ハイパーグラフ とよばれる。（ by Berge ） ここで P(V) は V のベキ集合である。

以下、便宜上、V ≠ φ を仮定することもある。

V の要素を 頂点（vertex）もしくは 点、E の要素を 辺（edge） という。
V を Γ の 頂点集合 、E を Γ の 辺集合 とよんでそれぞれ V(Γ)，E(Γ) で明記する。
μ は 接合写像 とよんで μ_Γ で明記する。
|V(Γ)| = p ，|E(Γ)| = q のとき (p, q) ハイパーグラフ とよぶ。|V(Γ)| を ν(Γ), |E(Γ)| を ε(Γ) で表すこともある。

μ(e) = μ(e') のとき e と e' は 平行である といい e // e' で表示する。
自身と異なる平行な辺をもつ辺を 多重辺（multiple edge）という。

かってな e∈E に対して s ≦ |μ(e)| ≦ t であるようなハイパーグラフを [s, t] ハイパーグラフ とよぶことにする。
[t, t] ハイパーグラフを t 一様(t-uniform)とよぶ。 t 一様で μ_Γ が単射なとき t 単純（t-simple）という。（単射とは１：１写像のことである．）

[1, 2] ハイパーグラフ G = (V, E) を単に グラフ とよぶ。
2 単純なハイパーグラフを 単純グラフ とよぶ。

以下、特に断わらない限りは、ハイパーグラフとしてはグラフのみを考える。

μ(e) = {u, v} のとき e は u と v を 結ぶ とよび e = {u, v} もしくは e = uv と表示する。u と v は e の 端点 とよばれる。
このとき e と v は 接合している（incident）とよばれ e inc v または v inc e と書く。
また、頂点 v が（いくつかの）辺の集合 A のある要素と接合しているとき v と A は 接合している とよぶ。

ひとつの辺の両端点や同一の頂点に接合している２つの辺は 隣接している（adjacent）とよび inc の代わりに adj で表示される。

|μ(e)| = 1 の辺 e もしくは {e} を ループ（loop）、|μ(e)| = 2 の辺 e もしくは {e} を リンク（link）という。

グラフが単純であるとはループも多重辺も持たないことである。

２つのグラフ G と H が 等しい G = H とは V(G) = V(H)，E(G) = E(H)，μ_G = μ_H のときで、
同型 G ～ H とは 全単射 θ：V(G)→V(H)，φ：E(G)→E(H) が存在して，μ_G(e) = {u , v} ⇔ μ_H(φ(e)) = {θ(u) , θ(v)} となるとき，とする。

G も H も単純なときは、G ～ H であることと全単射 θ：V(G)→V(H) が存在して uv ∈ E(G) ⇔ θ(u)θ(v) ∈ E(H) とは同値である。

同型な２つのグラフは「ラベリングだけの違い」と考えられるので、通常は区別しないで等しいものと見なされる。

接合写像 μ_H が μ_G の制限であるようなグラフ H は グラフ G の 部分グラフ（subgraph）とよばれ H ⊂ G とかかれる。G は H の 拡大グラフ ともよぶ。
V(G) = V(H) であれば H は G の 全域部分グラフ（spanning subgraph, 生成部分グラフ）もしくは 因子（factor）とよぶ。
２つの部分グラフの合併は自然に定義されるものとする。

S ⊂ V のとき、S を頂点集合とし両端点が S に属する G の辺全体を辺集合とする G の部分グラフを S が（点）誘導する G の部分グラフとよび G[S] または ＜S＞ で表示する。
誘導部分グラフ G[V - S] を G から S を 除去したグラフ とよび G - S とかく。
G - {v} を単に G - v とも表し G から頂点 v を 除去したグラフ とよぶ。

A ⊂ E のとき、A の各辺の端点とでできる G の部分グラフを A が（辺）誘導する G の部分グラフとよび G[A] または ＜A＞ で表示する。
(V(G), A) は G の A への 制限（restriction）とよび G|A で表示する。
G|(E - A) を G から A を 除去したグラフ とよび G - A とかく。
G - {e} を単に G - e とも表し G から辺 e を 除去したグラフ とよぶ。
G の頂点集合を変えずに除去の逆の操作をすることができるがそれは 付加 とよび G + A や G + e などで表す。

X ⊂ V(G) に対して G の頂点以外の点 v と X の各要素を辺で結んでえられる G の拡大グラフを v による X での ジョイン（join ，結）とよび v *_X G で表示する。 v *_V(G) G は単に v * G とも書く。
また、v *_φ G を G + v とも書き G に点 v を 付加したグラフ とよぶ。

V(G) ∩ V(H) = φ のグラフ H を使って H *_X G なども同様に定義される。

G の辺 e を１点に縮める操作を 初等縮約（elementary contraction）とよび、その結果得られるグラフを G/e で表し 辺 e による G の 縮約（contraction）もしくは 商グラフ（quotient graph）とよぶ。
初等縮約の合成を 縮約 とよび使われる辺の集合が S であればその結果得られるグラフを G/S で表し G の S による 縮約 もしくは 商グラフ とよぶ。
G の部分グラフ H について G/H とは G/E(H) のこととする。

|V(G/G)| = 1 のグラフ G を 連結している（connected）とよぶ。
頂点の集合や辺の集合は、誘導部分グラフが連結なとき 連結 とよぶことにする。

以下では頂点の集合や辺の集合とそれらが誘導する部分グラフについての用語を流用することがある。また、辺誘導部分グラフと辺の集合とを区別しなかったりそれらをユークリッド空間の点集合とみなすこともある。

グラフ G の包含関係に関して極大な連結部分グラフを 連結成分（connected component）または単に 成分 とよびその個数を ξ(G) で表示することにする。

ξ(G - v) ≧ ξ(G) + 1 となるような G の頂点 v は 切断点（cut vertex）もしくは 関節点（articulation vertex），
ξ(G - b) = ξ(G) + 1 となるような G の辺 b もしくは {b} は ブリッジ（橋、bridge），とよばれる。

辺集合 E(G) を２つの空でない E₁ と E₂ に分割して ＜E₁＞ と ＜E₂＞ が１点 v のみを共有するようにできるとき、v を G の 広義の切断点 という。

広義の切断点をもたない連結グラフを ブロック（block）とよぶ。
グラフ G の部分グラフ H はそれ自身がブロックで H を含むより大きなブロックがないとき G の ブロック とよばれる。

G の頂点 v に接合する辺の数を v の 次数（degree）とよび d_G(v) または deg_G(v) とかく。但しループは２回分数えるものとする。G が明確であるときは deg(v) などと略記する。

次数が 0 の頂点を 孤立点（isolated vertex），次数が 1 の頂点を 端点（end vertex），とよぶ。

G の頂点の次数を非増加にならべた列 (d₁, d₂, . . . , d_n) を G の 次数列（degree sequence）という。（ n = ν(G) ）

辺の除去や縮約および孤立点の除去を何回か繰り返してえられるグラフは マイナー とよばれる。

G の各頂点の次数の最小値を G の 最小次数 とよび δ(G), 最大値を G の 最大次数 とよび Δ(G)，とかく。

どの頂点の次数も k ，つまり δ(G) = Δ(G) = k ，であるグラフを k 正則（k-regular）とよぶ。 とくに 3 正則グラフは 3 価グラフ（trivalent graph）ともよばれる。
k 正則な因子を k 因子（k-factor）という。

例　0 と 1 よりなる長さ n の列を頂点とし１箇所だけ異なるとき辺で結んで得られるグラフ Q_n を n 次元立方体 もしくは単に n 立方体（n-cube）という。

Q_n は 2ⁿ 個の頂点と n 2^n-1 個の辺をもち n 正則。また、0 ≦ k ≦ n の任意の整数 k について k 因子を持つ。

奇数次数の頂点を 奇点 ，偶数次数の頂点を 偶点 とよぶ。

[ 定理 1.1 ]　どんなグラフにおいても奇点は偶数個存在する。

＜証明＞　(次数の総和) = 2×(辺の数) ゆえ。　　　　　　　　　　　　//

＜別証＞　簡単な場合分けで、辺の縮約によって奇点の個数の偶奇性は変化しないことがわかる。（ループ e の縮約は e の除去であることに注意．）

G/E(G) の奇点は 0 個で偶数個ゆえ、G の奇点も偶数個である。　　　　//

[ 注 ]　辺の除去でも同様に示される。 また、２章で更に別の証明を与える。

偶点のみからなるグラフを 偶グラフ（even graph），奇点のみからなるグラフを 奇グラフ（odd graph）とよぶ。

どの異なる２頂点も隣接している単純グラフは 完全グラフ（完備グラフ，complete graph）とよばれる。n 頂点の完全グラフは K_n で表示され、ε(K_n) = n (n - 1) / 2 である。

頂点集合 V が２つの部分集合 V₁ と V₂ で分割されて各辺が V₁ と V₂ を結んでいるようにできるグラフを ２部グラフ（bipartite graph ，２組グラフ ）とよぶ。V₁ と V₂ を 部集合（partite set）とよび G = G(V₁, V₂) とも書く。

部集合 X と Y についてどの X の要素と Y の要素も結ばれている単純２部グラフを 完全２部グラフ とよび、 |X| = m , |Y| = n であれば K_m,n で表示する。

グラフを表現する図形において辺を表す単純曲線どうしが共有する端点以外では交わらないとき、この図形をそのグラフの （幾何学的）実現 または 表現 という。
図形 X の部分集合として実現できるとき X に 埋め込み可能（embeddable）または 実現可能 とよぶ。

[ 定理 1.2 ]　すべてのグラフは３次元ユークリッド空間 R³ に埋め込み可能である。

＜証明＞　実際に埋め込みを構成する。

【 埋め込み法 （その１）】　平面上に図形表示して辺どうしの交差を立体交差に改変する。

【 埋め込み法 （その２）】　まず、頂点を x 軸上に重ならないように配置する。
次に、各辺に対応する x 軸を通る相異なる平面を選び、ループは接合する頂点以外の点を通らない円、リンクは２端点を結ぶ半円として実現する。　　　　//

平面 R² に埋め込めるグラフを 平面的グラフ（planar graph）、埋め込まれたグラフを 平面グラフ（plane graph）という。

平面グラフ G は平面の残りをいくつかの連結領域に分割する。それらを G の 面 または 領域 という。ただひとつ存在する非有界な面を 無限面 または 非有界面 または 外面 とよび、残りの面を 有限面 または 有界面 または 内面 とよぶ。

面 f の境界に含まれる辺の数を f の 次数 とよび d_G(f) または deg_G(f) とかく。但しブリッジは２回分数えるものとする。

面 f に対してその バウンダリー（境界，boundary）β(f) を f の境界に含まれるブリッジ以外の辺全体の集合として定義する。

平面グラフ G に対してはその 双対（平面）グラフ G^* が図のように自然に構成できる。

[ 注 ]　平面的グラフ G の２つの平面的実現 G₁，G₂ に対して G₁^*，G₂^* は同型とは限らない。

たとえば、図の G₁ と G₂ は同型であるが G₁^* と G₂^* は非同型。（∵ G₁ の無限面の次数は 5 であるが、G₂ は次数 5 の面を持たないから。）

双対グラフで対応する２つの概念を 双対概念（dual concept）という。
たとえば、辺の除去と辺の縮約、ループとブリッジ、偶グラフと２部グラフ、はお互いに双対な概念である。


[ 演習問題 ]　（ → 解答 ）

１． 次数列が ( 7, 6, 5, 4, 4, 4, 1, 1 ) である単純グラフは存在しないことを示せ。

２． 頂点数が２以上のどんな単純グラフも次数の等しい異なる２頂点を持つことを示せ。

３． n 頂点よりなる単純グラフ G のどの頂点の次数も (n - 1) / 2 以上であれば G は連結であることを示せ。

４． n 頂点よりなる単純グラフ G が (n - 1)(n - 2) / 2 + 1 本以上の辺をもっているなら連結であることを示せ。

５． 図の２つのグラフは同型であることを示せ。（Petersen グラフ）

６． ループをもたないグラフ G は辺数が ε(G)/2 以上の２部全域部分グラフをもつことを示せ。

７． f : V(G) → N ∪ {0} はすべての v ∈ V(G) に対して f(v) ≦ deg(v) であるとする。

G の全域部分グラフ Γ はすべての v ∈ V(G) に対して deg_Γ(v) = f(v) のとき G の f 因子（f-factor）とよばれる。

グラフ G に対してグラフ H で G が f 因子をもつことと H が 1 因子をもつことが同値であるようなのを構成せよ。

８． n 立方体 Q_n は２部グラフであることを示せ。

９． 平面グラフの非有界な面が丁度ひとつであることを示せ。（Hint： グラフは有界なので十分大きな半径の円に含まれる。）

１０． 頂点を３次元ユークリッド空間の点 (1, 1², 1³), (2, 2², 2³), (3, 3², 3³), . . . にすればどんな単純グラフも各辺が線分であるように空間に実現できることを示せ。

１１． 双対な概念の例を考えよ。（Hint： たとえば頂点の除去の双対は？）

１２． X ⊂ V(G) の X に対して X に属する頂点と V(G) - X に属する頂点を結ぶ辺の個数を f(X) とする。

任意の X, Y ⊂ V(G) について f(X) + f(Y) ≧ f(X∩Y) + f(X∪Y) が成り立つことを示せ。

１３． どんなグラフ G に対してもそれを部分グラフとする Δ(G) 正則なグラフが存在することを示せ。 またどんな２部グラフ G に対してもそれを部分グラフとする Δ(G) 正則な２部グラフが存在することを示せ。

グラフ G の（いくつかの）辺の集合 z は部分グラフ (V(G), z) = G - (E - z) が偶グラフのとき サイクル（輪体）とよぶ。（ いくつかの輪ゴムを放ってできるようなもの．）
たとえば、平面グラフの面のバウンダリーはサイクルとなっている。

集合 A と B の 対称差 AΔB とは (A - B)∪(B - A) もしくは (A∪B) - (A∩B) として定義されるもので A + B とも表示する。

対称差は偶奇性を反映する演算で、グラフ理論においては中心的な役割をもつ。

G の辺 e に対してその バウンダリー β(e) を

　　　　　　　　　　　 μ(e) ， e がリンクのとき
　　　　　β(e) = ｛
　　　　　　　　　　　　φ ， e がループのとき

と定め、G のいくつかの辺の集合 A のバウンダリー β(A) を Σ_e∈A β(e) とする。 β の代わりに ∂ を使ってもよいことにする。

[ 命題 2.1 ]

（１） 辺のかってな集合 A に対して |β(A)| は even（偶数）．
（２） 辺の集合 A に対して β(A) = { v | v は ＜A＞ の奇点 }．

[ 系 ]　定理 1.1

（∵） （２），（１）より |{ v | v は G の奇点}| = |β(E(G))| = even ．　　//

[ 定理 2.1 ]　辺の集合 z がサイクル　⇔　β(z) = φ．

[ 定理 2.2 ]　２つのサイクル z₁，z₂ に対してその対称差 z₁Δz₂ もサイクルである。

＜証明＞　１点 v に接合している z₁ の要素が 2s 個、 z₂ の要素が 2t 個、z₁∩z₂ の要素が m 個 とすると、v に接合している z₁Δz₂ の要素は 2s + 2t - 2m 個で even である。　　　　　//

＜別証＞　β(z₁ Δ z₂) = β(z₁)Δβ(z₂) = φΔφ = φ　ゆえ。　　//

この定理からグラフ G のサイクル全体は２元体 F₂ = {0 , 1} 上のベクトル空間を成し、G の サイクル空間 とよび Z(G) で表示する。（ 空集合 φ がゼロ元．）

グラフ G の（いくつかの）辺の集合 γ は商グラフ G/(E - γ) が２部グラフのとき（G の） カット もしくは コサイクル（cocycle）とよぶ。（ サイクルの双対概念で、イメージ的には、２部グラフの各頂点に連結グラフを埋め込んだグラフに対して元の２部グラフの辺集合がカット、つまりいくつかの連結部分グラフを横断的にカットしてるということ．）

G の頂点 v に対してその コバウンダリー（余境界，coboundary）δ(v) を

　　　　　δ(v) = { e ∈ E | e inc v ， e はリンク }

と定め、G のいくつかの頂点の集合 A のコバウンダリー δ(A) を Σ_v∈A δ(v) とする。

このコバウンダリーは国のバウンダリーの双対概念である。

δ(A) = δ(A^c) である。（ 但しここで A^c = V(G) - A ）

（∵）　δ(A) Δ δ(A^c) = δ(V) = φ　ゆえ。　　//

[ 補題 ]　連結グラフ G においては δ(X) = φ ⇒ X = φ または X = V(G)．

＜証明＞　X が φ でも V(G) でもないとすると X の要素 x と X^c の要素 y で隣接するのがとれる。すると xy ∈ δ(X) となり δ(X) = φ に反する。　　//

[ 定理 2.3 ]　連結グラフ G においては δ(A) = δ(B) ⇒ A = B または A = B^c．

＜証明＞　δ(A) = δ(B) とすると δ(A) Δ δ(B) = φ．

　　　　　∴ δ(A Δ B) = φ．
　　　　　∴ A Δ B = φ または A Δ B = V(G)．（∵ 補題より）
　　　　　∴ A = B または A = B^c．　　　　　　　//

[ 定理 2.4 ]　γ がカット　⇔　いくつかの頂点の集合 X があって γ = δ(X)．

＜証明＞　⇒；　２部グラフ G/(E - γ) の部集合のひとつを W とする。
縮約での W の原像を X とすれば γ = δ(X) となる。

逆；　γ は X と X^c を結ぶ辺の全体となるので。　　　　　//

[ 定理 2.5 ]　２つのカット γ₁，γ₂ に対してその対称差 γ₁Δγ₂ もカットである。

＜証明＞　定理 2.4 より γ_i = δ(X_i) （ i = 1, 2 ） と書ける。

このとき γ₁Δγ₂ = δ(X₁) Δ δ(X₂) = δ(X₁ΔX₂) で、再び定理 2.4 により、γ₁Δγ₂ もカットである。　　//

この定理からグラフ G のカット全体は２元体 F₂ = {0 , 1} 上のベクトル空間を成し、G の カット空間 もしくは コサイクル空間 とよび C(G) または Z^*(G) または Z^⊥(G) で表示する。

以下では、双対的な命題を述べなかったり述べても証明を省くことが多い。

[ 補題 ]　A ⊂ E(G) とする。

（１） かってな G のサイクル z に対して z - A は G/A のサイクルである。
（２） かってな G/A のサイクル z に対して、G のサイクル z~ で z~ - A = z となるのが存在する。（上昇補題（Going-up lemma））

＜証明＞　（１），（２）とも１辺による縮約の場合容易に成り立つから。　　//

[ 定理 2.6 ]　G の部分グラフ H に対して Z(G)/Z(H) と Z(G/H) は自然に同型である。

＜証明＞　補題の（１）から写像 Φ：Z(G) → Z(G/H) を Φ(z) = z - E(H) で定義できる。
補題の（２）からこの写像 Φ は全射である。

Φ(z₁Δz₂) = (z₁Δz₂) - E(H)
　　　　　　　= (z₁ - E(H))Δ(z₂ - E(H))
　　　　　　　= Φ(z₁)ΔΦ(z₂)

ゆえ Φ は線形である。

Ker Φ = Z(H) なので写像 Φ_*：Z(G)/Z(H) → Z(G/H) ，Φ_*(z + Z(H)) = z - E(H) ，は同型写像である。　//

グラフ G の（いくつかの）辺の集合 F は空でないサイクルを含まないとき （G の）森（forest）である もしくは （G で）非輪状（acyclic）という。

連結な森を 木（tree）または 樹木 とよぶ。
木の端点は 葉（leaf）ともよばれる。

全域部分グラフとなっている木を 全域木 もしくは 生成木 とよぶ。
連結グラフの極小な連結全域部分グラフは全域木となっている。

Z(G) を包含によるポセットと見たときの極大元を 極大サイクル（maximal cycle）とよぶ。
ポセット Z(G) は空集合 φ を最小元として持つが、φを除いて極小なサイクルを サーキット（閉路，circuit）もしくは 初等的サイクル（elementary cycle）もしくは 原子的サイクル（atomic cycle）とよぶ。

双対的に 極大コサイクル 、コサーキット（余閉路，余サーキット）などが定義されるが、コサーキットは ボンド（bond）ともよばれる。

ループはサイズが１のサーキット、ブリッジはサイズが１のコサーキットに他ならない。

グラフ G の頂点 u ，v に対して β(B) = {u}Δ{v} となる辺の集合 B を uv バインダー（uv-binder）とよぶことにする。極小な uv バインダーを uv パス（uv-path, uv 道）とよぶ。uv パスといったときに u から v への向きも考慮することがある。このとき、u を 始点 、v を 終点 とよぶ。

頂点 u ，v があって uv バインダーとなる辺の集合を バインダー とよぶ。パス も同様に定義される。これらは 端点 u , v を 結ぶ とよぶ。

パス π 上の２点 P と Q を端点として結ぶ π の部分的なパスを π(P, Q) で表示することもある。

サーキットやパスのサイズはそれらの 長さ ともよぶ。
サーキットの長さの最小値は 内周（girth）とよばれる。

u , v を結ぶパスの長さのうちの最小値を u , v の 距離（distance）といい dist(u, v) で表示する。

グラフ G の頂点 u ，v が uv バインダーを持つとき u ～ v とする。

[ 命題 2.2 ]　関係 ～ は同値関係である。

[ 定理 2.7 ]　u ～ v ⇔ u と v は同じ連結成分の頂点である。

[ 命題 2.3 ]　B₀ が uv バインダーのとき、{ B | B は uv バインダー} = B₀ + Z(G)．

[ 命題 2.4 ]　奇点が 2k 個のグラフの辺集合は k 個のバインダーに分割できる。

連結グラフ G の辺集合 E(G) が G の木（ resp. 森、パス ）であるとき G を 木（ resp. 森、パス ）ともよぶ。

[ 命題 2.5 ]

（１） 木 T のかってな２点 u, v に対して uv バインダーが一意的に存在しそれは uv パスである。
（２） 頂点数が２以上の木 T には２つ以上の端点が存在する。
（３） 端点を丁度２コ持つ木はパスである。

＜証明＞　（１） T は連結ゆえ uv バインダーが存在する。
異なる uv バインダー B₁, B₂ があったとすると B₁ Δ B₂ は空でないサイクルで不合理。

一意性から極小性が従う。

（２） サイズが最大のパスの端点は T の端点でもあるから。

（３） 端点を丁度２コ持つ木がパスでないとする。

それらの端点をむすぶ（一意的な）パスを縮約しても頂点数２以上の木で、端点が２コ以上存在する。これは不合理。　　　　　　　//

包含関係で極大な森を 極大森 もしくは ナーブ（神経、nerve）とよぶ。（ナーブというのはここだけの用語である。） 辺の集合 M がある極大森 N の補集合 E(G) - N となっているとき 補森 もしくは 補ナーブ とよぶ。

辺の集合 S がある全域木 T の補集合 E(G) - T となっているとき 補木 とよぶ。

[ 注 ]　全域森でも極大森とは限らないことに注意。

G のナーブの総数を τ(G) とかく。

次のようなカタチの帰納的な関係式はグラフ理論では良く出てくる。

[ 定理 2.8 ]　G のリンク e に対して、 τ(G) = τ(G - e) + τ(G/e) ．

＜証明＞　τ(G - e) = e を含まないナーブの総数 ，τ(G/e) = e を含むナーブの総数 ゆえ。　　　　　//

[ 系 ]　ループもブリッジももたないグラフ G においては τ(G) ≧ ε(G).

（∵） 非連結のとき、孤立点を除去しても τ(G) も ε(G) も不変ゆえ、孤立点は持たないとしてよい。このとき各連結成分でナーブの数も辺の数も２以上ゆえ連結として示せばよいことになる。

ε(G) = q = 0 のときＯＫ. q ≦ q₀ のときＯＫとする。

q = q₀ + 1 のとき；

G のどの辺 e についても G / e はループをもち G - e はブリッジをもつとき； G のブロックはサイズが２のサーキットで τ(G) = 2^q/2 ≧ q （q = 2, 4, 6, ...） で成り立つ。

G / e がループをもたないとき； G がブリッジをもたないから G / e ももたない。
よって G / e はループもブリッジももたない。また、e はブリッジでないから G - e は 全域木をもつ。

　　　　　∴ τ(G) = τ(G / e) + τ(G - e) ≧ q₀ + 1 = q

G - e がブリッジをもたないとき； G がループをもたないから G - e ももたない。
よって G - e はループもブリッジももたない。また G / e は全域木をもつ。

　　　　　∴ τ(G) = τ(G / e) + τ(G - e) ≧ q₀ + 1 = q　　　　//

[ 補題 ]　ナーブ N について、|N| = |V(G)| - ξ(G) ．

＜証明＞　G の連結成分を G₁, G₂, . . . , G_n とする。（ n = ξ(G) ）
T_i = N ∩ E(G_i) （ 1≦i≦n ） とおくと T_i は G_i の全域木となっている。

T_i について |T_i| = |V(G_i)| - 1 となっている。（ 演習問題 ）

∴ |N| = Σ |T_i| = |V(G)| - ξ(G)．　　　　　//

[ 定理 2.9 ]

（１） dim Z(G) = |E(G)| - |V(G)| + ξ(G) ．
（２） dim Z^*(G) = |V(G)| - ξ(G) ．

＜証明＞　（１） N をナーブ、H = G[N] とすると、定理 2.6 より、

Z(G/N) ～ Z(G)/Z(H) = Z(G)/{φ} ～ Z(G)

よって、補題より、

dim Z(G) = dim Z(G/N) = |E(G)| - ( |V(G)| - ξ(G) ) ．

（２）は（１）の双対である。　　　　　//

互いに素ないくつかの集合の合併をそれらの 素和（disjoint union）とよぶことにする。

次の命題は容易に示される。

[ 命題 2.6 ]

（１） サイクル ⇔ いくつかのサーキットの素和
（２） コサイクル ⇔ いくつかのコサーキットの素和

集合 A と B が |A ∩ B| ≡ 0 (mod 2) のとき even で交わる もしくは 直交する とよび A ⊥ B で表示する。

[ 補題 ]　グラフ G に対して、

（１） G は２部グラフ ⇔ どのサイクルのサイズも even ．
（２） G は偶グラフ ⇔ どのカットのサイズも even ．

＜証明＞　（１）⇒； どのサーキットのサイズも even ゆえ。

逆； １点 v を選ぶ。

v ～ w である頂点 w について vw バインダーのサイズの偶奇性は一定である。（∵ B₁ がサイズ even の vw バインダー，B₂ がサイズ odd の vw バインダーとすると、B₁ΔB₂ はサイズ odd のサイクルで不合理 ）

V₁ = { w | サイズ even の vw バインダーが存在する}，
V₂ = { w | サイズ odd の vw バインダーが存在する}，とおく。

V₁ のどの２点も V₂ のどの２点も非隣接である。（∵ たとえば V₁ の２点 w₁ と w₂ が辺 e で結ばれているとすると vw₁ バインダー B₁ ，vw₂ バインダー B₂ に対して B₁ΔB₂Δ{e} はサイズが odd のサイクルとなり不合理 ）

よって v を頂点とする連結成分は２部グラフである。他の連結成分も同様にして２部グラフなので G は２部グラフである。

（２）偶グラフ ⇔ どの頂点 v についても |δ(v)| は even
　　　　　　　　 ⇔ どのカットのサイズも even　　　　　　　//

[ 定理 2.10 ]

（１） G の辺の集合 z について、
z はサイクル ⇔ 任意のカット γ と even で交わる。
（２） G の辺の集合 γ について、
γ はカット ⇔ 任意のサイクル z と even で交わる。

＜証明＞　（１） ⇒； z∩γ は２部グラフ G/(E(G) - γ) のサイクルゆえ、補題により、|z ∩ γ| は even である。

逆： 頂点 v のコバウンダリーカット δ(v) とも even で交わっていることになるから。

（２）は（１）の双対である。　　　　　　　//

いくつかのサイクルの合併となっている辺の集合を サイクロイド（cycloid）、いくつかのカットの合併となっている辺の集合を コサイクロイド（cocycloid）、とよぶことにする。

[ 定理 2.11 ]　G の辺の集合 S について、

（１） S はサイクロイド ⇔ 任意のカット γ に対して |γ ∩ S|≠1．
（２） S はコサイクロイド ⇔ 任意のサイクル z に対して |z ∩ S|≠1．

＜証明＞　（１）⇒； S ∩γ≠φ とする。あるサイクル z ⊂ S ，z ∩γ≠φ．

|z ∩γ| は　even ゆえ |z ∩γ| ≧ 2　∴ |S ∩γ| ≧ |z ∩γ| ≧ 2
∴ |S ∩γ| ≠ 1

逆； S がサイクロイドでないとすると、S に含まれるサイクル全部の合併 A は S の真部分集合であることになる。

e ∈ S - A とする。
G - (E - S) で e はブリッジなので G/A で e はリンクである。
よって、G/A のカット γ で e を要素としてもつのが存在する。

この γ は G でもカットで |γ∩S| = 1 である。

（２）は（１）の双対で、 G - (E - S) の代わりに G/(E - S) を考えればよい。　//

[ 定理 2.12]　C₁ と C₂ が辺 e を要素として持つ異なるサーキットであるとき、C₁∪C₂ - {e} に含まれるサーキット C が存在する。（サーキット交換性質）

＜証明＞　C₁ΔC₂ が空でないサイクルであることからあきらか。　//

[ 定理 2.13]　C₁ と C₂ が辺 x を要素として持つ異なるサーキットであるとき、C₁ - C₂ のかってな要素 y に対して y ∈ C ⊂ C₁∪C₂ - {x} であるようなサーキット C が存在する。（狭義のサーキット交換性質）

＜証明＞　C₁, C₂, x, y が題意に対する |C₁∪C₂| が最小の反例とする。

サーキット交換性質からあるサーキット C₃ が存在して C₃ ⊂ C₁∪C₂ - {x} であるが、仮定より y は C₃ に属さない。

C₃∩(C₂ - C₁) が空だと C₃ は C₁ の真部分集合となって不合理ゆえ C₃∩(C₂ - C₁)≠φ である。

z を C₃∩(C₂ - C₁) の要素とする。

z ∈ C₂∩C₃, x ∈ C₂ - C₃ である。 また、y が C₂∪C₃ に属さないことから C₂∪C₃ は C₁∪C₂ の真部分集合である。

|C₁∪C₂| の最小性から、サーキット C₄ があって
x ∈ C₄ ⊂ (C₂∪C₃) - z ．

x ∈ C₁∩C₄ かつ y が C₂∪C₃ に属さないことから y ∈ C₁ - C₄ で、また C₁∪C₄ は C₁∪C₂ の真部分集合である。

よって、再び最小性からあるサーキット C₅ が存在して、
y ∈ C₅ ⊂ (C₁∪C₄) - x ．

C₁∪C₄ ⊂ C₁∪C₂ であることから
y ∈ C₅ ⊂ (C₁∪C₂) - x
であることになり、これは矛盾。　　　　　　　　　　　　　　　　　　　//

[ 定理 2.14]　グラフ G の２辺 x ，y について x = y か x と y を要素とするサーキットが存在するとき x R y として関係 R を定義するとこの関係 R は同値関係である。

＜証明＞　反射律 x R x , 対称律 x R y ⇒ y R x , はあきらか。
以下、推移律 x R y , y R z ⇒ x R z を示す。

x, y, z のうちに等しいのがあればあきらかに成立するので x, y, z はどの２つも等しくないとする。

{x, y} ⊂ C , {y, z} ⊂ D（ C , D はサーキット ）, しかし x R z ではないとする。
このような３つ組の中で (x, y, z) は |C ∪ D| が最小とする。

狭義のサーキット交換性質から

　　　　x ∈ C' ⊂ (C ∪ D) - y
　　　　z ∈ D' ⊂ (C ∪ D) - y

となるサーキット C' と D' が存在する。

C' ∩ (D - C) ≠ φ, D' ∩ (C - D) ≠ φ である。

最小性から C ∪ D' = C ∪ D なので D' - C = D - C
また |C' ∪ D'| ＜ |C ∪ D| なので C' ∩ D' = φ

∴ φ ≠ C' ∩ (D - C) = C' ∩ (D' - C) ⊆ C' ∩ D' = φ.　これは不合理。　　//

＜別証＞　x, y, z は相異なるとし、推移律 x R y , y R z ⇒ x R z を示す。

{x, y} を含むサーキットのひとつ C , {y, z} を含むサーキットのひとつ D とする。

z がループのとき； Ｄ = {z} で y = z.　よって Ｃ = {y} = Ｄ で x = y.
よって D（ = C ）は {x, z} を含む。

z がリンクのとき； y もリンクである。z = uv , y = pq とする。

D - z はパスで G[D - z] の u からたどって G[C] で最初に出会う頂点を P , v からたどって最初に出会う頂点を Q とする。

V(D) ∩ V(C) ⊃ {p, q} , p ≠ q なので P ≠ Q.

C は P ，Q により２つのパス π₁ と π₂ に分断される。
D も P ，Q により２つのパスに分断されそのうちの z を含む方を π とする。

C ∋ z ならＯＫゆえ C ∋ z でないとする。

π∪π₁ も π∪π₂ もサーキットでどちらかは {x, z} を含む。　　//

[ 定理 2.15]　グラフ G の２辺 x ，y について x = y か x と y を要素とするコサーキットが存在するとき x R^* y として関係 R^* を定義するとこの関係 R^* は R と一致する。

＜証明＞

x ≠ y , x R y のとき、あるサーキット C があって {x, y} ⊂ C .
C - {y} を含むナーブ N に対して γ(x ; N) ⊃ {x, y} .

次に x ≠ y , x R^* y のとき、あるコサーキット K があって {x, y} ⊂ K .
K は G - K の連結成分 G₁ と G₂ を結んでいるとする。

G₁ 中に x と y の端点を結ぶパス π₁ , G₂ 中に x と y の端点を結ぶパス π₂ が存在する。

π₁ ∪ π₂ ∪ {x, y} は {x, y} を含むサーキットである。　　　　//

[ 命題 2.7 ]

（１） グラフ G のサイクル z と交わらない辺の集合 X に対して z は G - X でもサイクルである。
（２） グラフ G のカット γ と交わらない辺の集合 X に対して γ は G / X でもカットである。


グラフ理論とくにグラフの構造論にとって、サイクルやカットがどのように分布しているかを調べることは重要である。

バウンダリー、コバウンダリーによって面はサイクル、頂点はカットに対応しているので、面や頂点に関する問題（たとえば色分け問題）はサイクルやカットで議論可能となり得る。




[ 演習問題 ]　（ → 解答 ）

１． 対称差 Δ に関する次の公式を証明せよ。

（１） (A Δ B) Δ C = A Δ (B Δ C)
（２） (A Δ B Δ C) ∪ X = (A ∪ X) Δ (B ∪ X) Δ (C ∪ X) （ Nagata の公式 ）
（３） (A ∇ B) ∇ C = A ∇ (B ∇ C) = A Δ B Δ C． 但し A ∇ B = (A Δ B)^c．

２． 連結グラフ G の生成木 T について |T| = |V(G)| - 1 であることを示せ。

３． グラフ G の辺の集合 T （の誘導部分グラフ）の頂点が n 個であるとき、次が同値であることを示せ。

（T1） T は木である.
（T2） T はサーキットを含まず |T| = n - 1.
（T3） T は連結で |T| = n - 1.
（T4） T は連結でどの要素も ＜T＞ のブリッジである.
（T5） ＜T＞ の異なる２点に対してそれらを結ぶバインダーが一意的に存在する.
（T6） ＜T＞ の異なる２点に対してそれらを結ぶパスが一意的に存在する.
（T7） T はサーキットを含まないが ＜T＞ に辺を付加すると丁度１個のサーキットを含むようになる.

４. グラフ G の辺の集合 N について次が同値であることを示せ。

（N1） N はナーブである.
（N2） どのコサーキットとも交わり、サーキットを含まない.
（N3） どのコサーキットとも交わり、そのような辺の集合のうち極小.
（N4） どのコサーキットとも交わり、|N| = |V(G)| - ξ(G).
（N5） サーキットを含まず、|N| = |V(G)| - ξ(G).

５. どんな木 T も少なくとも Δ(T) 個の端点を持つことを示せ。

６. T が k 個の辺をもつ木，G が δ(G)≧k の単純グラフであれば T は G の部分グラフとなることを示せ。

７. n ≧ 2 の正整数の非増加な列 ( d₁, . . . , d_n ) について、ある木の次数列となることと Σd_i = 2(n - 1) が同値であることを証明せよ。

８. τ(K_2,n) = n 2^n-1 であることを示せ。

９. 連結グラフにおける２つの最長なパスは頂点を共有することを示せ。

１０. 単純グラフ G のかってな点 v に対して v を始点とする長さ d(v) のパスがとれることを示せ。

１１. δ(G) ≧ 2 の単純グラフは長さが少なくとも δ(G) + 1 のサーキットをもつことを示せ。

１２. 連結グラフにおいて距離 dist(u, v) は距離空間の公理を満たしていることを示せ。

１３. T₁, T₂, . . . , T_k が木 T の部分木でどの２つも頂点を共有するとき全体として共有する頂点が存在することを示せ。

１４. 連結グラフの商グラフも連結であることを示せ。

後述するように、有名な四色定理は「ブリッジを持たない平面的グラフは２つのサイクルで cover できる」というのと同値であり、そのような２つのサイクルとしては包含関係で極大なサイクルを考えれば十分である。

ナーブの要素を 枝 ，補集合の要素を 弦 とよぶ。

[ 命題 3.1 ]　N を G のナーブとするとき、

（１） N の弦 x に対して N ∪ {x} は丁度ひとつのサーキットを含む。
（２） N の枝 x に対して N^c ∪ {x} は丁度ひとつのコサーキットを含む。

命題中のサーキットおよびコサーキットをそれぞれ N の弦 x に付随する 基本サイクル および N の枝 x に付随する 基本コサイクル とよび、それぞれ z(x ; N) および γ(x ; N) で表示する。

[ 命題 3.2 ]　N を G のナーブ、x と y をそれぞれ N の弦と枝とするとき、 x ∈ γ(y ; N) ⇔ y ∈ z(x ; N)

[ 定理 3.1 ]　グラフ G のナーブ N に対して、

（１） { z(x ; N) | x は N の弦 } はサイクル空間 Z(G) の基底である。
（２） { γ(x ; N) | x は N の枝 } はカット空間 Z^*(G) の基底である。

＜証明＞　（１） あきらかに独立でありサイズが |E(G)| - |V(G)| + ξ(G) なので定理 2.9 の（１）より基底であることになる。

（２）は（１）の双対である。　　　　　//

G の辺の集合 A に対して、dim Z(＜A＞) を A の サーキットランク ，dim Z^*(＜A＞) を A の コサーキットランク という。

[ 定理 3.2 ]

（１） G のナーブ N に対して z(N) = Σ_{x∈E(G) - N} z(x ; N) は極大サイクルである。
（２） G のかってな極大サイクル z に対して、あるナーブ N が存在して z = z(N)．

＜証明＞　（１） サイクル z(N) が極大でないと z を真部分として含むサイクル z' が存在することになる。

z Δ z' は N に含まれる空でないサイクルとなり不合理。

（２） z^c = E(G) - z は非輪状で z^c を含むナーブ N が存在する。

この N について z = z(N) となる。　　　　　//

[ 系 ]　τ(G) ≧ 極大サイクルの総数．

定理中の z(N) を N に 付随する極大サイクル または N が 決める極大サイクル とよぶ。
双対的に γ(N) = Σ_x∈N γ(x ; N) は極大コサイクルで N に 付随する極大コサイクル または N が 決める極大コサイクル とよぶ。

辺の集合 ζ は G/ζ が偶グラフのとき サイクライザー（cyclizer）とよぶことにする。サイクライザー全体のうち極小なのは 極小サイクライザー（minimal cyclizer）とよぶ。

[ 命題 3.3 ]

（１） 極大サイクルの補集合は極小サイクライザー。
（２） 極小サイクライザーの補集合は極大サイクル。

＜証明＞　（１）は定理 2.5 の補題の（１）から、（２）は同じ補題の（２）から容易に示される。　　　　//

サイズが odd（奇数）のカットを 奇カット とよぶ。

[ 命題 3.4 ]　サイクライザーである ⇔ 補集合が奇カットを含まない。

＜証明＞　ζ がサイクライザー ⇔ E(G) - ζ が G/ζ のサイクル
　　　　　　⇔ G/ζ は奇カットをもたない（by 定理 2.10）
　　　　　　⇔ G は E(G) - ζ に含まれる奇カットをもたない（by 命題 2.7）　//

[ 定理 3.3 ]　ナーブ N₁ と N₂ に対して次は同値である。

（１） z(N₁) = z(N₂)．
（２） N₁ ∩ N₂ はサイクライザー．

[ 定理 3.4 ]　孤立点を持たない単純グラフ G について次は同値。

（１） G は完全グラフ。
（２） G のどのコサーキットも極大カットである。

＜証明＞　（１）⇒（２）； G = K_n （ n ≧ 2 ）とし、 K を G のひとつのコサーキットで ω が K を真部分として含むようなカットとする。

ω' = ωΔK とおき、K = δ(V₁)，ω' = δ(V₂) （ V₁, V₂ ⊂ V(G) ）とする。 V_i （ i = 1, 2 ）が空でなくて V(G) の真部分であることはあきらか。

Case Ⅰ．V₁ ∩ V₂ ＝ φ； V_i の要素 v_i をえらぶと v₁v₂ ∈ K ∩ ω' で矛盾。

Case Ⅱ．V₁ ∩ V₂ ≠ φ； V₁ ∩ V₂ の要素 v と V(G) - V₁ の要素 w をえらぶ。

vw ∈ K で K ∩ ω' = φ ゆえ vw は ω' には属さない。
よって w ∈ V₂ であり、したがって V(G) - V₁ ⊂ V₂．

一方、かってな u ∈ V₁ について uw は K に属しているから uw は ω' には属していない。
よって u ∈ V₂ であり、したがって V₁ ⊂ V₂．

以上より V₂ = V(G) を得るが、これは矛盾である。

（２）⇒（１）； これは容易である。　　　　　　　　　　//

この定理からグラフ G の 非完全度 を定義することができる。



[ 演習問題 ]　（ → 解答 ）

１． 奇グラフのナーブ N の枝 x に対して次は同値であることを示せ。

　（１） x ∈ z(N)
　（２） N - x のどの連結成分も頂点数が even

２. 頂点を偶数個持つ連結な偶グラフの全域木の総数は even であることを示せ。（ Hint： 全域木を頂点とし２つの全域木が１辺どうしの入れ替えで移れるとき辺で結んだグラフを考える ）（ Eppstein ）

３. 頂点数と辺数の偶奇が等しい連結２部グラフの全域木の総数は even であることを示せ。

これからは、いくつかの辺の集合を フィギュア（図形，figure）ともよぶことにする。

A をグラフ G のフィギュア、x ∈ A とする。

A が （G の中で） x で特異である（ singular at x ）というのを サイクル z で z ∩ A = {x} となるのが存在するときとする。このサイクル z を A の x での 接サイクル（tangent cycle）とよぶ。サーキットである接サイクルは 接サーキット とよぶ。接サイクルが存在することと接サーキットが存在することは同値である。
A が x で特異でないとき x で正則（regular at x）とよぶ。

{ x ∈ A | A は x で特異} を Sing(A ; G) または単に Sing(A)，
{ x ∈ A | A は x で正則} を Reg(A ; G) または単に Reg(A)，で表示する。
Reg(A) = A であるフィギュアを 正則 という。

双対的に 余正則（coregular） などが定義される。

定理 2.11 より次を得る。

[ 定理 4.1 ]　G の辺の集合 S について、

（１） S は正則 ⇔ S はコサイクロイド．
（２） S は余正則 ⇔ S はサイクロイド．

A が x で特異なとき A の x での接サーキット C を使って A から A Δ C を作ることを A の x での 正則化 または 浄化（purging）とよぶ。

双対的に 余正則化 などが定義される。

[ 命題 4.1 ]　サイクライザーを正則化してもサイクライザー。

＜証明＞　ζ をサイクライザー、C を x での接サーキットとする。

ζ Δ C がサイクライザーでないとすると (ζ Δ C)^c は奇カット K を含む。
ζ はサイクライザーゆえ ζ^c は奇カットを含まないから x ∈ K であることになる。

K と C は even で交わるから (ζ Δ C) ∩ K ≠φ.
これは (ζ Δ C)^c ⊃ K に反する。　　　　　　　//

[ 命題 4.2 ]　z を グラフ G の極大サイクル、x を z に属するリンクとするとき次は同値である：

（１） z は x で特異である．
（２） z - x も G / x の極大サイクル.
（３） ∃！サーキット C , C ∩ z = {x}．（∃！ は一意的に存在するという記号）
（４） x を要素とするカット K は z に含まれない．

[ 定理 4.2 ]　グラフ G の極大サイクル z に対して、

（１） Reg(z) = z ∩ ( ∪_{z = z(N)} N )．
（２） M が z = z(M) であるような G のナーブのとき、Reg(z) = ∪_{x ∈ z ∩ M} γ(x ; M)．

[ 定理 4.3 ]　単純グラフは正則な極大サイクルを持つ。

グラフのサイクル空間とカット空間はグラフの一般論にとって欠かせないものではあるが、２元体 F₂ 上のベクトル空間としての構造だけでは勿論不十分である。

集合 A に対してそのベキ集合 P(A) は加法を対称差 Δ とすることで F₂ 上のベクトル空間となっていて、A の ベキ空間（power space）とよぶ。
ベクトル空間 ∑ はある集合 A のベキ空間 P(A) の部分空間となっているとき A 上の 集合空間（set space）とよぶことにする。

集合空間は包含関係 ⊂ によりポセットでもある。

ポセット P に対して { x ∈ P | x は P の極大元 }，{ x ∈ P | x は P の極小元 } をそれぞれ Max P，Min P で表示する。

[ 定理 5.1 ]　どんな集合空間 ∑ についても |Max ∑| は odd である。

＜証明＞　Max ∑ = {φ} のとき成り立つので Max ∑ ≠ {φ} とする。このとき空集合φは Max ∑ に属さない。

dim ∑ = n とすると |∑| = 2ⁿ である。
また、∑ ⊃ Max ∑ ≠ φ で、φ は ∑ に属し Max ∑ に属さないから、n ≧ 1 である。

∑ を頂点集合とする単純グラフ G = G(∑) を

　　　　　S₁ adj S₂ ⇔ S₁ ∩ S₂ = φ

として定義する。

M ∈ Max ∑ とする。M adj φ である。

φ ≠ S ∈ ∑ で M adj S とすると、M Δ S ∈ ∑ かつ M Δ S は M を真に含み M の極大性に反するから、 deg_G(M) = 1 である。
また、deg(φ) = 2ⁿ - 1 ≡ 1 (mod 2) （∵ n ≧ 1 ）

φ ≠ S ∈ ∑ - Max ∑ とする。∑ に属し S を真に含む S~ がとれる。
S Δ S~ は空でなくて ∑ に属し、 S adj φ かつ S adj (SΔS~) .
∴ deg(S) ≧ 2.

deg(S) = |{ X ∈ ∑ | X adj S }| で { X ∈ ∑ | X adj S } は ∑ の部分空間ゆえ、deg(S) ≧ 2 であることから、deg(S) は even .

以上と定理 1.1 より |Max ∑| は odd である。　　//

[ 系 ]　どんなグラフの極大サイクルも奇数個存在する。

ベクトル空間 V の部分集合 C はある部分空間 W のコセット（剰余類）であるとき単に V における コセット（coset）ともよぶことにする。

２元体 F₂ 上のベクトル空間 V におけるコセット C に対して
S(C) = { x | x は C の偶数個の要素の和 } は部分空間で C は S(C) のコセットになっている。

[ 系 ]　ベキ空間 P(E) におけるコセット C が最小元をもてば |Max C| は odd.

（∵） C の最小元を M とする。

写像 Φ_M：C → S(C) , X ├→ M Δ X , は順序同型ゆえ、定理 5.1 より、|Max C| は odd.　　//

[ 系 ]　ベキ空間 P(E) におけるコセット C が最大元をもてば |Min C| は odd.

（∵） E + C = { E Δ X | X ∈ C } も S(C) のコセットになる。

写像 Φ_E：C → E + C , X ├→ E Δ X = X^c , は反順序同型ゆえ、上記の系より、|Min C| は odd.　　//

[ 命題 5.1 ]　F₂ 上のベクトル空間 V の空でない部分集合 C について次は同値。

（１） C は V におけるコセット。
（２） a，b，c ∈ C ⇒ a + b + c ∈ C．

[ 系 ]　グラフ G のフィギュア A が x で特異なとき、A の x での接サイクル全体（の集合）は集合空間 Z(G) におけるコセットである。
また uv バインダーの全体はべき空間 P(E(G)) においてサイクル空間 Z(G) のコセット。

∪∑ = { e | ある ∑ の要素 z があって、 e ∈ z } を ∑ の 台 とよぶ。

集合空間 ∑ の台 ∪∑ の部分集合 S に対して { z ∈ ∑ | z ⊃ S } を C(S) で表示する。

[ 系 ]　集合空間 ∑ の台 ∪∑ の部分集合 S に対して C(S) は ∑ におけるコセットである。

次の美しい定理が成り立つ。（合作）

[ 定理 5.2 ]　集合空間 ∑ におけるかってなコセット C において、
| Max C | ≡ | Min C | （ mod 2 ）.

＜証明＞　Max C ，Min C を部集合とする単純２部グラフ G = G( Max C ，Min C ) を

　　　　　MN ∈ E(G) ⇔ M ⊃ N （ M ∈ Max C , N ∈ Min C ）

として定義する。

M ∈ Max C について集合 { S ∈ C | S ⊂ M } は M + { S ∈ C | S ⊂ M } のコセットで deg M = |Min { S ∈ C | S ⊂ M }| ,
N ∈ Min C について集合 { S ∈ C | S ⊃ N } は N + { S ∈ C | S ⊃ N } のコセットで deg N = |Max { S ∈ C | S ⊃ N }| ,
となっている。

定理 5.1 の系より deg M も deg N も odd である。

よって、定理 1.1 より、|Max C| ≡ |Min C| (mod 2) である。　　　　//

[ 系 ]　グラフ G の辺 x に対して、x を含む極大サイクルの総数と x を含むサーキットの総数の偶奇性は一致する。

[ 系 ]　偶グラフのひとつの辺を含むサーキットの総数は odd である。

集合 A 上の集合空間 ∑ の要素を サイクル ，A の要素を 辺 とよぶ。

A 上の集合空間 ∑ に対して ∑^⊥ = { ω⊂ A | ∀z∈∑，ω⊥z } も A 上の集合空間で ∑ の （直交的）双対 とよび、その要素を ∑ の コサイクル とよぶ。∑^⊥ を ∑^* とも書く。

A 上の集合空間 ∑ と X ⊂ A に対して、
∑/X = { z - X | z ∈ ∑ } は A - X 上の集合空間で ∑ の X による 縮約 、
∑|X = { z ∈ ∑ | z ⊂ X } は X 上の集合空間で ∑ の X への 制限 、とよぶ。

[ 命題 5.2 ]　A 上の集合空間 ∑ と X ⊂ A に対して、
(∑|X)^⊥ = ∑^⊥/(A - X) ，(∑/X)^⊥ = ∑^⊥|(A - X).

[ 命題 5.3 ]　グラフ G に対して、
Z(G)/X = Z(G/X) ，Z^*(G)|X = Z^*(G|X).

集合族 S は ∪S のどんな異なる２要素 x, y に対しても x を要素とし y を要素としない S の要素が存在するとき 分離的（separable）とよぶ。
また、∪S のどんな異なる２要素 x, y に対してもどちらか一方を含み他方を含まない S の要素が存在するとき 準分離的（quasi separable）とよぶ。

[ 命題 5.4 ]　集合空間に対しては、分離的 ⇔ 準分離的 である。

[ 命題 5.5 ]　集合空間 ∑ について次は同値である。

（１） 分離的．
（２） |ω| = 2 であるようなコサイクルをもたない。

次の定理は合作である。

[ 定理 5.3 ]　分離的集合空間 ∑ において、|Atom ∑| ≧ |∪∑|.

[ 系 ]　|ω| = 2 であるようなカットをもたないグラフでは、サーキットのほうがブリッジでない辺よりも多いか等しい。

ベクトル空間の部分空間 W が生成する部分空間を ＜W＞ で表示する。

[ 定理 5.4 ]　A 上の集合空間 W に対して A ∈ ＜W ∪ W^⊥＞.（ Gallai, Chen ）

＜証明＞　X ∈ ＜W ∪ W^⊥＞^⊥ ⇔ X ∈ W^⊥ ∩ W^⊥⊥ = W ∩ W^⊥
∴ ＜W ∪ W^⊥＞ = (W ∩ W^⊥)^⊥.

Y ∈ W ∩ W^⊥ とすると |Y| = |Y ∩ Y| ≡ 0 (mod 2).
∴ A ∈ (W ∩ W^⊥)^⊥ = ＜W ∪ W^⊥＞.　　　　　　//

[ 系 ]

（１） 任意のグラフ G に対して V(G) の分割 V(G) = V₁ ∪ V₂ で G[V₁] も G[V₂] も偶グラフとなるのが存在する。
（２） 任意のグラフ G に対して V(G) の分割 V(G) = V₁ ∪ V₂ で G[V₁] は偶グラフ G[V₂] は奇グラフとなるのが存在する。

＜証明＞　（１） 定理から E(G) ∈ ＜Z(G) ∪ Z^*(G)＞ なのでサイクル z とカット γ で E(G) = z + γ となるのが存在する。
よって E(G) はサイクル z とカット γ の素和となる。

(V(G), z) の各連結成分は偶グラフで孤立点は適当に割り振って γ の部集合に即して所望の V(G) の分割がえられる。

（２） G^~ = v * G に対して、（１）より、V(G^~) の分割 V(G^~) = U₁ ∪ U₂ で G^~[U₁] も G^~[U₂] も偶グラフとなるのが存在する。

v ∈ U₂ として一般性を失わない。

V₁ = U₁ ，V₂ = U₂ - {v} とすると所望の分割となる。　　//