Question

【題目】給定空間中十個(gè)點(diǎn)，其中任意四點(diǎn)不在一個(gè)平面上，將某些點(diǎn)之間用線段相連，若得到的圖形中沒(méi)有三角形也沒(méi)有空間四邊形，試確定所連線段數(shù)目的最大值.

Answer 1

【答案】15

【解析】

以這十個(gè)點(diǎn)為頂點(diǎn)、所連線段為邊得一個(gè)十階簡(jiǎn)單圖G.

下面證明：圖G的邊數(shù)不超過(guò)15.

設(shè)圖G的頂點(diǎn)為，共有k條邊，用表示頂點(diǎn)的度.

若對(duì)均成立，則.

假設(shè)存在頂點(diǎn)滿足.不妨設(shè)，且與均相鄰.于是，之間沒(méi)有邊，否則，就形成三角形.從而，之間恰有n條邊.

對(duì)每個(gè)，至多與中的一個(gè)頂點(diǎn)相鄰（否則，設(shè)與 相鄰，則就對(duì)應(yīng)了一個(gè)空間四邊形的四個(gè)頂點(diǎn)，這與題設(shè)條件矛盾）.從而，與之間的邊數(shù)至多為

.

在這個(gè)頂點(diǎn)之間，由于沒(méi)有三角形，由托蘭定理，知至多有條邊.因此，圖G的邊數(shù)為

.

如圖所示給出的圖共有15條邊，且滿足要求.

綜上，所求邊數(shù)的最大值為15.