圖着色上限

Question

維基百科國圖的着色以下的上界：

但我不明白這是爲什麼。給予。信息不清楚給我。

有人能幫助我嗎？

Answer 1

在 here

它是如此清楚，順便句子是

在一個最佳的着色必須有每對顏色類之間的曲線圖的米 邊緣中的至少一個

我會分解它，並使每個部分更清晰。

• 在一個最佳的着色：這意味着你發現了圖形着色，你不能減少任何更多的顏色從它，如果減少一種顏色會有兩種顏色相近的鄰居。

• 必須是每對顏色類之間的曲線圖的m邊緣中的至少一個：從所述第一部分考慮最佳的着色，它有兩種顏色例如A和B有A之間沒有邊緣彩色節點和B彩色節點（，不同於此語句），則我們可以將所有顏色節點的顏色更改爲顏色B，但它與第一​​條語句相矛盾。

• 由前兩個聲明，我們有公式：

  • 我們在這個着色X(G)(X(G) - 1)/2對顏色。
  • 所有這些對之間至少有一條邊。
  • 所以我們X(G)(X(G) - 1) /2小於等於m所以我們有：