Question

【題目】已知空間9點集，其中任意四點不共面.在這9個點間聯結若干條線段，構成一個圖G，使圖中不存在四面體.問圖G中最多有多少個三角形？

Answer 1

【答案】27

【解析】

在一個n個點的空間圖中不存在三角形，則其邊數不超過.

證明:設這n個點為，其中從引出的邊數最多，不妨設共有k條:.依條件，不存在三角形，那么，點之間沒有邊相連.從而，空間圖中每條邊均至少有一個端點為中的點而每個至多引出k條邊.因此，總邊數小于或等于k

下面證明空間9點集M中，若任意4點不共面，在這9點間聯結若干條線段，如果圖G中已有（至少）28個三角形，則至少有一個四面體.

用反證法.

假設不存在一個四面體，在9點集中，由抽屜原理知，其中必有一點為至少個三角形的頂點.從而，由這個點至少引出5條邊，設這個點為

(1).若從點引出5條邊，依題意，由于沒有四面體，那么，由這5個點構成的子圖中沒有三角形.由前面的結論知，這個子圖中至多有條邊.從而.以為頂點的三角形至多有6個，矛盾.

（2）若從點引出6條邊，類似(1)，至多有個三角形以為頂點,矛盾.

（3）若從點引出7條邊，由于沒有四面體，可知這7個點構成的子圖中沒有三角形,這個子圖至多有條邊.從而，以為頂點的三角形至多有12個，不以為頂點的三角形必以點為一個頂點.類似地也至多有12個三角形，那么，三角形總數小于或等于12×2-24<28，矛盾.

（4）若從點引出8條邊，這時,，A這8個點構成的子圖中沒有三角形.由前面的結論知，至多有條邊.從而，原圖G中至多有16個三角形,矛盾.

于是，滿足要求的三角形至多有27個.

將9點集M分成三組，，，使同組中任兩點不連線，而不同組中的兩點均連線，這樣有個三角形,當然沒有四面體.