極大平面的グラフの頂点彩色と四色問題①

（注）この極大平面的グラフの頂点彩色と四色問題の記事の内容や定理の証明は、「グラフ理論序説」の内容をそのままお借りしているところがあります。

１，グラフ

　グラフGとは、集合の対(V(G)、E(G))である。

　V(G)をグラフGの頂点集合、V(G)の元を頂点という。

　E(G)をグラフGの辺集合、E(G)の元を辺という。

　しばしば、V(G)、E(G)をそれぞれV、Eで表す。

　グラフは、頂点集合Vが有限集合か無限集合かによって、有限グラフあるいは無限グラフという。

　辺がe、e={u、v}のとき、辺は頂点とを”結ぶ”という。

　グラフのうち、2つの頂点を2本以上の辺(多重辺)で結ぶことを認めるグラフを多重グラフと呼ぶ。

　グラフのうち、同じ頂点を結ぶ辺(ループ)を認めるグラフをループグラフと呼ぶ。

　グラフのうち、頂点集合が有限でループも多重辺も認めないグラフを単純グラフと呼ぶ。

　以下、グラフといえば単純グラフを意味するものとする。

　辺e={u、v}のとき、辺eに対して頂点u、vを辺eの端点という。

　このとき、辺eは端点u、vに”接続している”といい、頂点u、vは辺eに”接続している”という。

　また、頂点uと頂点vは互いに”隣接している”という。

　グラフGの頂点集合の要素の個数をGの位数、辺の本数をGのサイズという。

　以下では、位数をp、サイズをqで表す。このとき、Gを(p、q)グラフと呼ぶ。

　Gの頂点vに接続するGの辺の個数をvの次数といい、dG(v)で表す。

　グラフGがグラフHに同型であるとは、V(G)からV(H)への1対1対応fで

　　{u、v}がE(G)の元であるとき、そのときに限り、{f(u)、f(v)}がE(H)の元である

　ことを満たすものが存在することである。

　定理1・1(握手補題)

　　Gは(p、q)グラフとし、V(G)={v1、v2、・・・、vp}とする。このとき、次の式が成り立つ。

　　　Σ{p、i=1}dG(vi)=2q

　　(証明)

　　　グラフGの次数の総和Σ{p、i=1}dG(vi)は、Gの中で、各辺の両端で1回ずつ合計2回数えている。したがって、次数の総和は辺の本数qの2倍である。(証明終わり)

　グラフGにおいて、歩道とは、Gの頂点と辺とが交互に現れる有限列

　　W=v0e1v1e2v2・・・ekvk

　であって、各辺ei(1≦i≦k)は頂点vi-1とviを端点としてもつようなものである。

　頂点v0、vkをそれぞれ歩道の始点、終点と呼ぶ。始点と終点が一致するとき、Wは”閉じている”という。

　すべての辺が異なる歩道を小道といい、すべての頂点が異なる歩道を道という。

　歩道や道の辺の個数をそれらの長さという。

　閉じている小道は回路といい、閉じている道は閉路という。

　グラフG内の2頂点u、vに対してG内のu-v道が存在するとき、u、vは”連結している”という。

　グラフGのどの2頂点も連結しているとき、Gは連結グラフであるという。

　連結でないグラフは非連結グラフである。