Question

【題目】求最大實數，使得對任意階簡單圖，有不等式，其中，為圖的邊數，為圖中三角形的個數.

Answer 1

【答案】

【解析】

先證明一個引理.

引理 設階簡單圖有條邊，個三角形.則.

證明 因為階簡單圖中，個三角形共有條邊，且每條邊至多出現在個三角形當中，所以，.

回到原題.

首先考慮特殊的階完全圖，有.

令，則.

下面用數學歸納法證明：對任意階簡單圖成立.

當時，結論顯然成立.

假設當時，結論成立.

當時，取為階簡單圖中度數最小的頂點，設其度數為，并設余下的個點構成的簡單圖中有條邊，個三角形.則由引理知.①

由歸納假設知.②

因為點度數最小，所以，.③

設與點相鄰的個頂點之間連有條邊，這條邊每條和點都形成一個三角形.故只需證明

. ④

易知，，.⑤

因此，.

將式①、③代入上式得.⑥

又由式⑤知.⑦

由式②、⑥、⑦知式④成立，即當時，結論成立.

從而，對所有，結論成立.

因此，.