如何證明Kn完全拆分成較小完全圖至少需要n個

1樓：波波兒爸

如果是邊不交並的拆分，圖論裡Matching的概念加上Hall』s Theorem 足夠了。

不正式的說一下。構造乙個bipartite, 左邊乙個集是點，右邊另乙個集是不交較小完全子圖的邊集，以 incident structure 為bipartite 的連線。

宣告，存在乙個matching cover 所有點。右邊都是K2 是trivial 的。另一種情況，如果有至少乙個點沒被cover，該點所屬的n-1條邊就會分配到n-1個點所屬的各完全子圖中，有兩種情況，只屬於1個完全子圖，或者屬於兩個或以上的完全子圖，兩種都能推出矛盾。

證完matching cover, 引用Hall』s theorem 就可得證。

2樓：猹猹

「若n點完全圖的邊集可以分解成k份的不交並，每份組成乙個完全子圖，則k≥n。」

這是個組合經典小結論，在2023年由De Bruijn-Erds給出。

這個結論一般由finite linear space的語言表述，故為組合設計方面的初學者所熟知(組合其他門類的博士生應該也是知道的，不知道的請重學)。

本回答姑且做個復讀機，把這個證明翻譯成圖論語言簡述一下(原諒我不會用知乎打latex)：

我們記Kn分解出的完全子圖為A(1),...,A(k)，其點數依次為a(1),...,a(k)。對任意點x，記d(x)為包含x的A(i)的個數。

現設x不是某A(i)中的點。

為了用完全子圖囊括所有邊xy(y∈A(i))，包含x的A(j)個數d(x)必然滿足d(x)≥a(i)。這是因為每個A(j)(j≠i)最多只能包含乙個y∈A(i)，否則就會有一邊同在A(i),A(j)中的情況發生。

現考慮反證法，假設點數n≥k。由d(x)≥a(i) ，顯然-a(i)k≥-d(x)n，兩邊同加nk，有：(n-a(i))k≥(k-d(x))n。稱此式為(*)式吧。

因此：這個k≥k的式子(本質是算兩次)告訴我們，不等式取等，故剛才得到的(*)式取等，即-a(i)k=-d(x)n，故n=k。

再捋一下邏輯，我們剛剛是假設n≥k，之後得到了n=k。這說明n≤k，故證畢。

注：這個結論中的不等關係(k≥n)顯然可以取等，只要取乙個n-1點完全圖，再把剩下的n-1邊視作n-1個K2即可。但是，這並不是唯一的分法。

至少，對於形如q+q+1的n，可由投影平面給出乙個n個全為q+1點完全圖的分解：

如n=7時，把上圖各自含3個點的7條線(6條直線1個圓)視作7個K3，它就是K7的乙個取k=n的分解。