グラフ理論

質問

Gを頂点数ｎ、変数ｍの単純グラフとし、PG(k)をGの彩色多項式をし、PG(k)のk^n-1の係数が－ｍであることを示せ。
という証明問題なんですが、なんで－ｍになるのかがわかりません。
すみませんが教えてください。

回答No.2

Tacosan · ベストアンサー

無駄があるかもしれませんが:
まず, G を n頂点の空グラフ (辺を持たないグラフ) とすると, P(G, k) = k^n です. 定義から計算してください.
で, 次に n頂点のグラフG に対し P(G, k) が k に関する n次多項式で k^n の係数が 1になることを (頂点数と辺の数に関する) 帰納法で示します.
辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k) ですが, 右辺に出てくる G-e, G/e はどちらも G より小さいグラフです. G-e は G と頂点数は同じで, 辺は 1本減っています. また, G/e は G より頂点が 1個少なく, また辺も少なくとも 1本は減っています. だから右辺には帰納法が適用できて P(G-e, k) = k^n + o(k^n), P(G/e, k) = k^(n-1) + o(k^(n-1)) です. つまり P(G, k) も k^n + o(k^n) です.
これだけ用意すれば, あとは辺の本数に関する帰納法がまわります.

お礼

ありがとうございます。
あと「 o(k^n) 」のoとは何を意味しているのでしょうか？

回答No.3

Tacosan

おっと, ここでは o(k^n) は「k^n より次数の低い項」の意味で使ってます.
ちょうど「最高次だけ考えればいい」ところだったので, 最高次以外の項を無視するために使いました.

お礼

ありがとうございました！！
なんとかやってみます！！

回答No.1

Tacosan

普段使わないのでちょっと調べたんだけど, 彩色多項式の性質をどこまで使っていいのかなぁ?
卑怯だけど,
・任意の辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k)
・n頂点のグラフ G に対し, P(G, k) は k に関する整数係数 n次多項式かつ k^n の係数は 1
・P(empty graph, k) = k^n
を使っていいなら一瞬ですね.
もしくは, 帰納法かなぁ?

お礼

ええと、この前の問題が「P(G, k) = P(G-e, k) - P(G/e, k)となることを示せ」という問題なので、
誘導の意味もあって「任意の辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k)」は使えると思います。他の２つに関してはすみませんが不明です…

補足

あと「任意の辺 e に対し P(G, k) = P(G-e, k) - P(G/e, k)」
だけでも証明は出来るんでしょうか？