如何證明所有可平面圖總有一種方法把所有邊畫成黑白，使其無任何奇數同色環？

12-06

自己想出來的：

不能存在任何同色三角形，也不能存在長度為五、七、九。。。
比如這樣：

看似很簡單明顯，隨便畫一下都能找到辦法分配黑白edge滿足這條件。

但是K5之類的最簡單的non-planar graph就不行了，無論怎麼分配，總存在某同色奇數長度cycle。

思考良久無法自證，感覺也許有很簡潔明了的思路？拜託。。。或者請舉證反例？

（這個問題看似不重要，但證明了確實有很重要的意義和後果，暫時先不說）

這個結論可由四色定理證明

四色定理：每個平面圖的色數至多是4
即任意一個平面圖G，可以用最多四種顏色對G的頂點染色，使相鄰的頂點不同色

不妨設G的色數是4(當G的色數小於4時可類似證明)
於是可用四種顏色對G的頂點染色，使相鄰的頂點不同色
將同色的頂點放在一起，形成四個幾個集合A,B,C,D，如圖
同一個集合內的點之間沒有邊

G=(V,E)
於是可以構造兩個生成子圖G1，G2
G去掉A與B之間的邊，C與D之間的邊，得到G1
G去掉屬於G1的邊，得到G2

顯然G1，G2都是二部圖
於是G1，G2中均不存在奇圈
回到G中，將屬於G1的邊塗成白色，屬於G2的邊塗成黑色，則不存在相同顏色的奇圈

看到平面，的時候我進來了
看完之後我想我還是默默的走開吧。。。

這居然是個外國人提的問題。。

這是四色定理的等價命題，等價性很簡單。所以為什麼總想搞個大新聞呢。

平面圖的邊把整個平面劃分為N個互不重合的基本塊，找出其中所有邊數為偶數的，這些塊的所有頂點構成集合A，把它們的所有邊染成黑色。其他所有頂點構成集合B。
如果一個A中的點和B中的點相連，則分情況：
若A中的點連接的這樣的邊只有一條，則該邊染白色；
否則按黑：白=1:1的數量染，並保證對於所有僅由B中的點構成的基本塊，如果所有頂點都與A中的同一個點相連，那麼這些連接線不為同一種顏色。
如果B中的兩點之間相連，而且都與A中的同一點相連，則連接這兩點的線為黑色。
接下來考慮B中的點，讓其構成的全部都是無同色環的奇數的基本塊，而且與A中同一點相連的兩點沒有奇數白色迴路。