Question

【題目】已知空間9點(diǎn)集，其中任意四點(diǎn)不共面.在這9個(gè)點(diǎn)間聯(lián)結(jié)若干條線(xiàn)段，構(gòu)成一個(gè)圖G，使圖中不存在四面體.問(wèn)圖G中最多有多少個(gè)三角形？

Answer 1

【答案】27

【解析】

在一個(gè)n個(gè)點(diǎn)的空間圖中不存在三角形，則其邊數(shù)不超過(guò).

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

下面證明空間9點(diǎn)集M中，若任意4點(diǎn)不共面，在這9點(diǎn)間聯(lián)結(jié)若干條線(xiàn)段，如果圖G中已有（至少）28個(gè)三角形，則至少有一個(gè)四面體.

用反證法.

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

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

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

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

（4）若從點(diǎn)引出8條邊，這時(shí),，A這8個(gè)點(diǎn)構(gòu)成的子圖中沒(méi)有三角形.由前面的結(jié)論知，至多有條邊.從而，原圖G中至多有16個(gè)三角形,矛盾.

于是，滿(mǎn)足要求的三角形至多有27個(gè).

將9點(diǎn)集M分成三組，，，使同組中任兩點(diǎn)不連線(xiàn)，而不同組中的兩點(diǎn)均連線(xiàn)，這樣有個(gè)三角形,當(dāng)然沒(méi)有四面體.