推 plover :阿..Since there are n-1 neighbors of v in G-v and 04/23 01:06
→ plover :(G-v)* in total. 原來是最多有(n-1)個neighbors 04/23 01:06
→ plover :謝謝 m(_ _)m 04/23 01:07
→ hcsoso :對對，因為不用管自己~ 04/23 01:07
※ 引述《plover (○(*￣中肯￣*)○)》之銘言：
: Prove that χ(G) + χ(the complement of G) ≦ n(G) + 1.
: From West, Introduction to Graph Theory, 2/e, Exercise 5.1.41
: 很有趣，可以玩一玩 @@a
好久沒有寫圖論，來試試看...
We'll prove the statement by induction on n(G).
Denote G* as the complement of G.
For n(G) = 1, the statment is trivially true.
Assume for every G with n(G) < n the statement holds.
Now for a graph G with n(G) = n, take an arbitrary vertex v in V(G).
Consider G-v, by induction hypothesis, χ(G-v) + χ((G-v)*) <= n(G-v) + 1 = n.
Since χ(H) <= χ(H-v) + 1 for every non-null graph H,
either χ(G) = χ(G-v) or χ(G*) = χ((G-v)*) will makes the desire inequality
hold: χ(G) + χ(G*) <= χ(G-v) + χ((G-v)*) + 1 <= n + 1.
The remain case is that both χ(G) = χ(G-v) + 1 and χ(G*) = χ((G-v)*) + 1.
This happens only when v adjacents to at least χ(G-v) neighbors in G-v,
otherwise there are still usable colors remain. Same as to (G-v)*,
there are at least χ((G-v)*) neighbors of v.
Since there are n-1 neighbors of v in G-v and (G-v)* in total,
we have χ(G-v) + χ((G-v)*) <= n - 1;
now the desire inequality still holds.
By induction the original statement holds for every G. Q.E.D.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.15.15