グラフ理論について

質問

全然分からなくて困っています。誰か助けてください。

１．グラフKn,Kn￣、Km,n,Cn,Tn〔Ｔnは位数nの木〕の染色数をそれぞれ求めよ。

２．グラフKn,Km,n,Cn,Tnの辺染色数をそれぞれ求めよ。

３．オイラーの多面体公式を証明せよ。

４．以下の問題を証明せよ。

〔１〕頂点数が３以上の平面グラフGが極大平面グラフであるための必要十分条件は、Gのすべての領域が三角形であることである。

〔２〕４頂点以上の極大平面グラフGにおいて、

　　　　　　△〔G〕
　　不等式　Σ　〔6-i〕Ni =12 〔Ni = {次数がiの頂点の数}〕が成立する。

〔３〕４頂点以上の平面的グラフには、次数５以下の頂点が存在する。

〔４〕K5,K3,3は非平面的グラフである。

〔５〕平面的グラフは５-彩色可能である。

回答No.2

Tacosan

なるほど, せいぜい「あんまり理解できてない」くらいの理解度だってことはわかった.

たとえば, 「補グラフ」を理解しているなら「単に『補グラフ』とだけ書いても無意味」ということまでわかっていなきゃいけない. つまり
＿
Knは補グラフ
なんて書き方はしないはず.

そして,
・「グラフKn,Kn￣、Km,n,Cn,Tn〔Ｔnは位数nの木〕」とはなんなのか
とわざわざ書かせたのは, これら (Kn￣ は「補グラフ」では全く無意味なのでさしあたり無視) に関しては「染色数はわかるはず」だから. 辺彩色数はちょっと微妙なところがあるけど, 染色数は簡単にわからないとだめ.

回答No.1

Tacosan

とりあえず
・「グラフKn,Kn￣、Km,n,Cn,Tn〔Ｔnは位数nの木〕」とはなんなのか
・「染色数」や「辺染色数」はどのように定義されているのか
・「オイラーの多面体公式」とはどのような公式なのか
・「極大平面グラフ」とはいかなる条件を満たすグラフなのか
・「△〔G〕」が何を表すのか
くらいはきちんと書いてほしい.

もちろん, それができないならこんなところで聞いている場合じゃない.

補足

Knは完全グラフ
＿
Knは補グラフ
Km,nは完全二部グラフ
Cnはサイクル
TnはN点からなる木
木：閉路(サイクル)を含まない連結グラフのこと

染色数と辺染色数は一番小さい数を答えとする。

オイラーの多面体公式とは、連結な平面グラフの頂点数Ｖ、辺数Ｅ、面数Ｆに対してV-E＋F = 2となる公式
△(G)
　∑ の△(G)は最大次数のこと
i = 3
極大平面グラフとは平面グラフに可能なかぎり辺を加えてできる平面グラフ