グラフ理論入門 補１ 定理集

定理

• 定理1.1.1
  
  • グラフGの頂点をv1,v2,...,vpとし、d1,d2,...dpをそれぞれ頂点の次数とする。qをGの辺の個数とすると、次が成り立つ：
    
    • d1+d2+...+dp=2q.
• 定理1.1.2 Havel, Hakimi
  
  • 次の2つの非負整数列を考え、数列(1)は大きいものから順に並んでいるものとする。
    
    • (1)x,t1,t2,...,ts,d1,...,dn
    • (2)t1-1,t2-1,...,ts-1,d1,...,dn
  • このとき、数列(1)がグラフ的であるための必要十分条件は、数列(2)がグラフ的であることである。
• 定理1.3.1
  
  • グラフGが連結で、p頂点とq辺を持つならば、
    
    • p<=q;1.
• 定理1.3.2
  
  • Gをp頂点、q辺を持つ木とすると、
    
    • p=q+1.
• 定理1.3.3
  
  • グラフGが連結で、p=q+1ならば、Gは木である。
• 定理1.3.4
  
  • 少なくとも1辺を持つ木は、少なくとも２つの端頂点を持つ。
• 定理1.3.5
  
  • グラフGが木であるための必要十分条件は、Gの任意の2頂点について、それらを結ぶ道がただ1つ存在することである。
• 定理1.3.6
  
  • 連結グラフGは、全域木を含む。

• 定理2.1.1
  
  • 臨界なグラフは連結である。
• 定理2.1.2
  
  • 任意のグラフGは、χ(H)＝χ(G) であるような、臨界部分グラフHを含む。(ただし、今、HはGの部分グラフであって、真部分グラフではない)
• 定理2.1.3
  
  • Gが彩色数χで臨界ならば、各頂点の次数は少なくともχ-1である。
• 定理2.1.4
  
  • p頂点とq辺を持つグラフGが臨界で、Gの彩色数がχならば、次の関係式が成り立つ：
    
    • (χ-1)p<=2q.
    • ※グラフGがK4または、Wn(ただしnは奇数)と同型な部分グラフを含むならば、χ(G)>=4であることを『知って』いる。
• 定理2.1.5(Erdos-Lovasz)
  
  • 任意の2つの整数m,n>=2に対して、彩色数nを持ち、内周がmを超えるようなグラフが存在する。
• 定理2.1.6
  
  • グラフGが2部グラフであるための必要十分条件は、Gのすべてのサイクルが偶数の長さを持つことである。
• 定理2.2.1
  
  • Gをグラフとする。G の固有辺彩色のために必要な色の数は、Gの頂点の最大次数以上である。
• 定理2.2.2(VIzing)
  
  • k-正則グラフの辺彩色数はkかk+1である。
• 定理2.2.3
  
  • K2nの辺彩色数は2n-1である。
• 定理2.2.4
  
  • K2n-1の辺彩色数は2n-1である。
• 定理2.3.1(Lucas)
  
  • 完全グラフK2n+1はn個のハミルトンサイクル(長さ=2n+1)に分解可能である。
• 定理2.3.2
  
  • K2nはn-1個のハミルトンサイクルと1個の1-因子に分解可能である。
• 定理2.3.3
  
  • K2nはn個のハミルトン道に分解可能である。
• 定理2.3.4
  
  • 完全グラフK2nは、その長さが1,2,3,...2n-1であるような、2n-1個の道に分解可能である。
• 定理2.3.5
  
  • スナーク(辺彩色数4の3-正則グラフ)はハミルトンサイクルを持たない。
• 定理2.4.1
  
  • Gを連結グラフとする。Gが木であるための必要十分条件は、Gの任意の辺が橋であることである。
• 定理2.4.2
  
  • 偶数個の辺を持つ連結グラフは、長さ2の道と同型な部分グラフに分解可能である。

• 定理3.1.1(Euler)
  
  • 準グラフGがオイラー回路を持つならば、Gは連結で、すべての頂点の次数は偶数である。
• 定理3.1.2(Hierholzer)
  
  • 準グラフGが連結で、Gのすべての頂点の次数が偶数ならば、Gはオイラー回路を持つ。
• 補題3.1.3
  
  • 準グラフGにおいて、どの頂点の次数も正で偶数ならば、Gの任意の頂点はある回路の上にある。
• 定理3.1.4
  
  • 準グラフGが4-正則ならば、Gは2つの2-因子に分解される。
• 定理3.1.5
  
  • 準グラフGがサイクルに分解可能であるための必要十分条件は、Gのすべての頂点の次数が偶数であることである。
• 定理3.1.6
  
  • 準グラフがオイラー小径を持つための必要十分条件は、Gが連結で、ちょうど2つの奇数の頂点を持つことである。
• 定理3.1.7(Listing)
  
  • Gを連結な準グラフとし、次数が奇数の頂点がちょうど2h個(ただしhは0ではない)あるとする。このとき、Gにはh個の小径が存在して、Gの各辺はこれらの小径のうちのちょうど1つに含まれる。つまり、Gはh個の小径に分解可能である。さらに、hより少ない個数の小径で、このような性質を持つものは存在しない。
• 定理3.2.1
  
  • 次数が偶数の正則グラフは橋を持たない。
  • →より一般的に、頂点の次数がすべて偶数であるグラフは橋を持たない。
• 定理3.2.2
  
  • 橋を持つような3-正則グラフは、3個の1-因子には分解不可能である。
• 定理3.2.3(Petersen)
  
  • 橋を持たない3-正則グラフGは、1-因子1つと2-因子2つとに分解される。
• 定理3.2.4
  
  • 橋を持たない3-正則グラフは、長さ3の道に分解可能である。
• 定理3.2.5
  
  • 4-正則グラフは3-正則な部分グラフを含む。

• 定理4.1.1
  
  • n頂点を持ち、彩色数kを持つ最大のグラフは、n=n1+n2+...+nk で、|ni-nj|<=1である正整数について、完全k部グラフKn1,n2,...,nkである。
• 定理4.1.2(Turan)
  
  • n頂点を持ち、Kn+1と同型な部分グラフを含まない最大のグラフは、n=n1+n2+...+nkで|ni-nj|<=1である正整数について、完全k部グラフKn1,n2,...,nkである。
• 定理4.1.2*
  
  • n頂点を持ち、三角形を含まない最大のグラフは、n=n1+n2で|n1-n2|<=1である正整数について、完全2部グラフKn1,n2である。
• 補題4.1.3
  
  • GがKn+1を含まないn頂点グラフならば、Gと同じ頂点集合を持つk部グラフHが存在して、Gのどの頂点zについても
    
    • degG(z)<=degH(z)
  • が成り立つ。
• 定理4.2.1
  
  • ペテルセングラフは、唯一の5-ケージである。
• 定理4.2.2
  
  • ヒーウッド(Heawood)グラフは唯一の6-ケージである。
• 定理4.3.1(Ramsey)
  
  • 任意の正整数nに対して、次の性質を持つ整数r(n)が存在する：r(n)個の頂点を持つ完全グラフの、赤と青による任意の辺彩色は、赤Knかまたは青Knのいずれかを含む。
• 定理4.3.2
  
  • 任意の正整数mとnに対して、ラムゼー数r(m,n)が存在して、赤と青によるKr(m,n)の任意の辺彩色は、赤Kmかまたは青Knのいずれかを含む。さらに、r(m,n)は次の不等式を満たす：
    
    • r(m,n)<=r(m-1,n)+r(m,n-1).

• 定理5.2.1
  
  • Knの全域木の個数は、次式で与えられる：
    
    • s(Kn)=n**n-2.
• 定理5.3.1
  
  • グラフK2,nの全域木の個数は、n 2**(n-1)である。
• 定理5.3.2
  
  • グラフK3,nの全域木の個数は、n**2 3**(n-1)である。
• 定理5.3.x
  
  • 完全2部グラフKm,nの全域木グラフの個数は、
    
    • s(Km,n)=m**(n-1) n**(m-1).

• 定理6.1.1
  
  • 2ではない、nについて、Kn,nはマジックである。
• 定理6.1.2
  
  • 2部グラフGが2つのハミルトンサイクルに分解可能ならば、Gはマジックである。
• 定理6.1.3
  
  • グラフGが2つのマジックな全域部分グラフG1とG2に分解され、しかもG2が正則ならば、Gはマジックである。
• 定理6.2.1
  
  • グラフGが2つのハミルトンサイクルに分解可能ならば。Gは保守的である。
• 定理6.2.2(キルヒホッフの全流の法則)
  
  • Gがラベル付けされた有向グラフで、特別な1頂点aを除くすべての頂点においてキルヒホッフの流率が成り立っているならば、キルヒホッフの流率は頂点aにおいてもまた成り立つ。
• 定理6.2.3
  
  • Gが2つの部分グラフH1,H2に分解され、H1が保守的でH2が強意で保守的ならば、Gも保守的である。さらに、H1とH2がともに強意で保守的ならば、Gも強意で保守的である。
• 定理6.2.1*
  
  • Gが2つのハミルトンサイクルに分解可能ならば、Gは強意に保守的である。
• 定理6.2.4
  
  • Gをn頂点を持つグラフとする。nが奇数であって、Gが3つのハミルトンサイクルに分解可能であるならば、Gは強意で保守的である。
• 定理6.2.5
  
  • nが奇数で、n>=5ならば、Knは保守的である。
• 定理6.2.6
  
  • n>=3について、n本のスポークを持つ車輪グラフWnは保守的である。
• 定理6.2.7
  
  • nが偶数で、n>=4ならば、Knは保守的である。

• 定理8.1.1(オイラーの多面体公式)
  
  • p頂点とq辺を持つ連結グラフの平面図がr個の領域を持つならば、
    
    • p-q+r=2
  • が成り立つ。
• 定理8.1.2
  
  • p>=3とする。Gが極大平面的グラフで、p頂点とq辺を持つならば、次の等式が成り立つ：
    
    • q=3p-6.
• 定理8.1.3
  
  • p>=3とする。Gを、p頂点とq辺を持つ平面的グラフとすると、次の関係式が成り立つ：
    
    • q<=3p-6.
• 定理8.1.4
  
  • 完全グラフK5は平面的でない。
• 定理8.1.5
  
  • p>=3とする。Gをp頂点とq辺を持つ平面的2部グラフとすると、次の関係が成り立つ：
    
    • q<=2p-4.
• 定理8.1.6
  
  • 完全2部グラフK3,3は平面的でない。
• 定理8.1.7
  
  • 平面的グラフは、次数が5以下の頂点を少なくとも1つ含む。
• 定理8.1.8
  
  • Gはp頂点とq辺を持つ極大平面的グラフとし、p>=4とする。piで、次数iの頂点の個数を表す。このとき、次の式が成り立つ：
    
    • 3p3+2p4+p5=12+p7+2p8+3p9+4p10+... .
• 定理8.2.1(Tait, 1880)
  
  • もし正規地図が4色で彩色できるならば、その地図の辺は3色で彩色できる。
• 補題8.2.2
  
  • 平面上の有限個の単純閉曲線について、これらの曲線によって決まる領域は2色で彩色できる。
• 定理8.2.3(Tait)
  
  • 正規地図の辺が3色で固有辺彩色できるならば、この地図は4色で彩色できる。
• 定理8.2.4
  
  • 正規地図において、その辺が3色によって固有彩色可能ならば、その頂点は、次の性質(*)を満たすように黒と白でラベル付け可能である：
  • (*)任意の国の国境の一周するとき、国境上の黒頂点の個数から白頂点の個数を引いた数は常に3の倍数である。
• 定理8.2.5
  
  • 定理8.2.4の逆も正しい；つまり、次が成り立つ。
    
    • 正規地図Mにおいて、その頂点を次の性質(*)を満たすように黒と白でラベル付け可能ならば、Mの辺は３色に---よって固有辺彩色可能である。
    • (*)Mの任意の国の国境を一周するとき、国境上の黒頂点の個数から白頂点の個数を引いた数は常に3の倍数である。
• 定理8.2.6(4色定理)
  
  • 任意の正規地図は4色で彩色可能である。
• 定理8.2.7
  
  • 任意の3-正則で、橋を持たない平面的グラフは、3色によって固有辺彩色可能である。
• 定理8.2.8
  
  • 少なくとも4頂点を持つ極大平面的グラフの頂点は、高々4色によって彩色可能である。
• 定理8.2.9
  
  • 平面的グラフの頂点は、高々4色によって彩色可能である。
• 補題8.3.1
  
  • 地図には、互いに隣接する5ヶ国は存在しない。
• 定理8.3.2(5色定理)
  
  • 正規地図は5色で彩色可能である。
• 定理8.4.1(Wagner)
  
  • 平面的グラフは、辺がすべて線分となるような平面図を持つ。

• 定理9.1.1
  
  • グラフGが、K5の細分または、K3,3の細分を部分グラフとして含むならば、Gは非平面的である。
• 定理9.1.2(Kuratowski)
  
  • グラフGが非平面的ならば、GはK5の細分または、K3,3の細分を部分グラフとして含む。
• 定理9.1.3
  
  • K4の平面上の単純図は高々1つの交差点を持つ。
• 定理9.1.4
  
  • 完全グラフK6の交差点は3である；cr(K6)=3.
• 定理9.2.1
  
  • p頂点とq辺を持つグラフG について、次が成り立つ：
    
    • θ(G)>=q/(3p-6).
• 定理9.2.2
  
  • p頂点とq辺を持つ2部グラフGについて、次が成り立つ：
    
    • θ(G)>=q/(2p-4).
• 定理9.2.3
  
  • 完全グラフの厚みは、次のようになる：
    
    • θ(Kn)=floor((n+7)/6), nが9,10でないとき；n=9 or 10のときは 3.
• 定理9.2.4(Hartsfield,Jackson,Ringel)
  
  • n>=10ならば、
    
    • σ(Kn)=ceiling((n-3)(n-4)/6).
• 定理9.2.5(Jackson,Ringel)
  
  • m,n>=2について、
    
    • σ(Km,n)=ceiling((m-2)(n-2)/2).
• 定理9.3.1(Heawood, 1890)
  
  • 任意の2帝国地図は12色で彩色可能であり、また、12色が必要な2帝国地図が存在する。
• 定理9.3.2(Heawood)
  
  • 任意のm帝国地図は、6m色で彩色可能である。
• 定理9.3.3(Heawood,Jackson,Ringel)
  
  • 任意のm>1に対して、互いに隣接する6mのm帝国からなる地図が存在する。

• 定理10.1.1
  
  • グラフの頂点vが次数dを持つならば、vに関しては(d-1)!通りの異なる循環が存在する。
• 定理10.1.2
  
  • p頂点とq辺を持つ連結グラフの循環をρとすると、次の不等式が成り立つ：
    
    • p-q+r(ρ)<=2.
  • さらに、この左辺の交互和
    
    • p-q+r(ρ)
  • は、常に偶数である。
• 定理10.2.1
  
  • グラフGが橋を持つならば、Gの任意の循環ρについて、この橋はρによって誘導される回路の1つに両方向で現れる。
• 定理10.2.2
  
  • 平面的グラフの部分グラフは平面的である。
• 定理10.2.3
  
  • 完全2部グラフK3,3は平面的でない。
• 定理10.2.4
  
  • 完全グラフK5は平面的ではない。
• 定理10.2.5
  
  • 3個以上の頂点を持つ極大平面的グラフは連結で橋を持たない。
• 定理10.2.6
  
  • 極大平面的グラフの平面的循環によって誘導される回路はすべて長さ3を持つ。
• 定理10.2.7
  
  • p頂点(p>=3)とq辺を持つ極大平面的グラフにおいては、
    
    • q=3p-6
  • が成り立つ。
• 定理10.2.8
  
  • Gを、p頂点(p>=4)を持つ、極大平面的グラフとし、Gの次数iの頂点の個数をpiで表す。すると、次式が成り立つ：
    
    • 3p3+2p4+p5=12+p7+2p8+3p9+...
• 定理10.2.9
  
  • 平面上に辺を交差させずに描くことができる連結グラフは、平面的循環を持つ。