數學傳播

由 $n$ 個點及所有兩點之間的線段組成的圖形, 稱為 $n$ 點完全圖, 記為 $K_n$。 若 $K_n$ 中的所有線段僅用紅色或藍色染色, 稱為二染色。對 $K_n$ 中由三個點連接而成的三角形, 若三條邊用相同的顏色染色, 則稱之為同色三角形。

有關二染色的 $K_n$ 問題是圖論與組合數學中的經典而有趣的問題, 在數學奧林匹克競賽中也經常出現相關的試題。

例1: 任意六個人中, 必有3個人相互認識或相互不認識。 (1947年第48屆匈牙利數學奧林匹克試題)。

例2: 十七個人兩兩通信, 他們在通信中討論的僅有三個不同問題, 且任意兩個人通信時只討論一個問題。則至少有3個人互相通信時討論的是同一個問題。 (1964年第6屆IMO試題)。

例3: 將某個圓周上的九個不同點之間的36條邊分別用紅色或藍色染色。若其中的任意三點之間都至少有1條紅色邊, 則存在4個點, 它們之間的邊均為紅色邊。 (1976年第8屆加拿大數學奧林匹克試題)。

上述試題中, 例 1 與圖論中的 Ramsey 定理等價。

定理1: 在二染色的 $K_6$ 中, 必存在1個同色三角形。

1958年《美國數學月刊》將例1列為征解問題E1321, 引起很大反響。定理1的一個熟知的加強為Goodman定理。

定理2: 在二染色的 $K_6$ 中, 必存在2個同色三角形。

本文將進一步探究定理2中的兩個同色三角形的性質, 給出如下結果。

定理3: 在二染色的 $K_6$ 中, 下面的 (1)、 (2)、 (3)必有一個成立。

• (1) 存在 2 個同色三角形, 這兩個三角形有一條公共邊, 從而有相同的顏色。
• (2) 存在2個同色三角形, 這兩個三角形僅有一個公共的頂點, 並有不同的顏色。
• (3) 僅存在2個同色三角形, 這兩個三角形沒有公共的頂點, 但是有相同的顏色。

首先證明兩個引理。

引理1: 在某個二染色的 $K_6$ 中, 若任意的2個同色三角形均沒有公共邊, 但存在2個同色三角形, 它們有一個公共頂點, 則在這個二染色的 $K_6$ 中, 必存在2個同色三角形, 它們有一個公共頂點, 但是有不同的顏色。

證明: 將此二染色的 $K_6$ 中的6個頂點記為 $A_1,A_2,\cdots,A_6$, 則存在2個同色三角形, 不妨記為 $\triangle A_1A_2A_3$ 和 $\triangle A_3A_4A_5$, 它們有一個公共的頂點 $A_3$。

當 $\triangle A_1A_2A_3$ 與 $\triangle A_3A_4A_5$ 的顏色不同時, 引理1成立。

當 $\triangle A_1A_2A_3$ 與 $\triangle A_3A_4A_5$ 的顏色相同時, 不妨設 $\triangle A_1A_2A_3$ 和 $\triangle A_3A_4A_5$ 均是紅色三角形。 先證明 $A_1A_4$, $A_1A_5$, $A_2A_4$, $A_2A_5$ 均是藍色邊。

若 $A_1A_4$ 是紅色邊, 則$\triangle A_1A_3A_4$ 是一個紅色三角形, 它與 $\triangle A_1A_2A_3$ 有公共邊 $A_1A_3$, 與 $\triangle A_3A_4A_5$ 有公共邊 $A_3A_4$, 矛盾。 故 $A_1A_4$ 是藍色邊。

若 $A_1A_5$ 是紅色邊, 則$\triangle A_1A_3A_5$ 是一個紅色三角形, 它與 $\triangle A_1A_2A_3$ 有公共邊 $A_1A_3$, 與 $\triangle A_3A_4A_5$ 有公共邊 $A_3A_5$, 矛盾。 故 $A_1A_5$ 是藍色邊。

若 $A_2A_4$ 是紅色邊, 則$\triangle A_2A_3A_4$ 是一個紅色三角形, 它與 $\triangle A_1A_2A_3$ 有公共邊 $A_2A_3$, 與 $\triangle A_3A_4A_5$ 有公共邊 $A_3A_4$, 矛盾。 故 $A_2A_4$ 是藍色邊。

若 $A_2A_5$ 是紅色邊, 則$\triangle A_2A_3A_5$ 是一個紅色三角形, 它與 $\triangle A_1A_2A_3$ 有公共邊 $A_2A_3$, 與 $\triangle A_3A_4A_5$ 有公共邊 $A_3A_5$, 矛盾。 故 $A_2A_5$ 是藍色邊。

參見圖1 (圖中的實線代表紅色邊, 虛線代表藍色邊), 若 $A_1A_6$ 是藍色邊, 則當 $A_4A_6$ 也是藍色邊時, $\triangle A_1A_4A_6$ 是一個藍色三角形, 它與 $\triangle A_1A_2A_3$ 有公共的頂點 $A_1$, 與 $\triangle A_3A_4A_5$ 有公共的頂點 $A_4$, 引理1成立。當 $A_4A_6$ 是紅色邊時, 必有 $A_5A_6$ 是藍色邊 (否則, 若 $A_5A_6$ 是紅色邊, 則 $\triangle A_4A_5A_6$ 是一個紅色三角形, 它與 $\triangle A_3A_4A_5$ 有公共邊 $A_4A_5$, 矛盾), 從而 $\triangle A_1A_5A_6$ 是一個藍色三角形, 它與 $\triangle A_1A_2A_3$ 有公共的頂點 $A_1$, 與 $\triangle A_3A_4A_5$ 有公共的頂點 $A_5$, 引理1成立。

同理, 若 $A_5A_6$ 是藍色邊, 則當 $A_2A_6$ 也是藍色邊時, $\triangle A_2A_5A_6$ 是一個藍色三角形, 它與 $\triangle A_1A_2A_3$ 有公共的頂點 $A_2$, 與 $\triangle A_3A_4A_5$ 有公共的頂點 $A_5$, 引理1成立。 當 $A_2A_6$ 是紅色邊時, 必有 $A_1A_6$ 是藍色邊 (否則, 若 $A_1A_6$ 是紅色邊, 則 $\triangle A_1A_2A_6$ 是一個紅色三角形, 它與 $\triangle A_1A_2A_3$ 有公共邊 $A_1A_2$, 矛盾), 從而 $\triangle A_1A_5A_6$ 是一個藍色三角形, 它與 $\triangle A_1A_2A_3$ 有公共的頂點 $A_1$, 與 $\triangle A_3A_4A_5$ 有公共的頂點 $A_5$, 引理1成立。

參見圖2, 當 $A_1A_6$ 與 $A_5A_6$ 均是紅色邊時。若 $A_2A_6$ 是紅色邊, 則 $\triangle A_1A_2A_6$ 是一個紅色三角形, 它與 $\triangle A_1A_2A_3$ 有公共邊 $A_1A_2$, 矛盾。若 $A_4A_6$ 是紅色邊, 則 $\triangle A_4A_5A_6$ 是一個紅色三角形, 它與 $\triangle A_3A_4A_5$ 有公共邊 $A_4A_5$, 矛盾。 故 $A_2A_6$ 與 $A_4A_6$ 均是藍色邊。從而 $\triangle A_2A_4A_6$ 是一個藍色三角形, 它與 $\triangle A_1A_2A_3$ 有公共的頂點 $A_2$, 與 $\triangle A_3A_4A_5$ 有公共的頂點 $A_4$, 引理1成立。

綜上所述, 引理1成立, 證畢。

引理2: 在某個二染色的 $K_6$ 中, 若任意的2個同色三角形均沒有公共的頂點, 則在這個二染色的 $K_6$ 中, 僅存在2個同色三角形, 它們沒有公共的頂點, 但是有相同的顏色。

證明: 將此二染色的 $K_6$ 中的6個頂點記為 $A_1,A_2,\cdots,A_6$, 則存在2個同色三角形, 不妨記為 $\triangle A_1A_2A_3$ 和 $\triangle A_4A_5A_6$ , 它們沒有公共的頂點。

若此二染色的 $K_6$ 中存在另一個同色三角形, 則其必分別與 $\triangle A_1A_2A_3$、 $\triangle A_4A_5A_6$ 有公共的頂點, 矛盾。故此二染色的 $K_6$ 中僅存在2個同色三角形, 即 $\triangle A_1A_2A_3$ 與 $\triangle A_4A_5A_6$。

當 $\triangle A_1A_2A_3$ 與 $\triangle A_4A_5A_6$ 的顏色相同時, 引理2成立。

當 $\triangle A_1A_2A_3$ 與 $\triangle A_4A_5A_6$ 的顏色不同時。 不妨設 $\triangle A_1A_2A_3$ 是紅色三角形, $\triangle A_4A_5A_6$ 是藍色三角形。

若存在 $i=1,2,3$, 使得 $A_iA_4$, $A_iA_5$, $A_iA_6$ 中至少有2條藍色邊, 則此二染色的 $K_6$ 中又存在一個藍色三角形, 矛盾。

否則, 對所有的 $i=1,2,3$, $A_iA_4$, $A_iA_5$, $A_iA_6$ 中均至少有2條紅色邊, 故 $A_iA_j$ 中至少有6條紅色邊, 其中 $i=1,2,3$, $j=4,5,6$。 從而存在 $j=4,5,6$, 使得 $A_1A_j$, $A_2A_j$, $A_3A_j$ 中至少有2條紅色邊, 故此二染色的 $K_6$ 中又存在一個紅色三角形, 矛盾。

綜上所述, 引理2成立, 證畢。

根據定理2、引理1和引理2可知定理3成立。

下面給出三個圖例, 分別有且僅有定理3中的 (1)、 (2) 或 (3)一種情形存在。圖中的實線代表紅色邊, 虛線代表藍色邊。

在圖3中, 只有2個同色三角形, 即 $\triangle A_1A_2A_3$ 和 $\triangle A_2A_3A_4$ , 它們均是紅色三角形, 並有公共邊 $A_2A_3$, 即僅有定理3中的情形 (1)成立。

在圖4中, 只有2個同色三角形, 即 $\triangle A_1A_2A_3$ 和 $\triangle A_3A_4A_5$, 其中 $\triangle A_1A_2A_3$ 是紅色三角形, $\triangle A_3A_4A_5$ 是藍色三角形, 它們的顏色不同, 且只有一個公共的頂點 $A_3$, 即僅有定理3中的情形 (2)成立。

上面的三個圖例表明, 在二染色的 $K_6$ 中, 除了定理3中的 (1)、 (2)和 (3)必有一個成立以外, 其它情形可以不存在。

---本文作者邊欣任教天津市天津師範大學數學系, 李忠民任教天津市天津大學管理與經濟學部---