[TrauBo]

Định lý 1: (Định lý Mantel)

Cho G là một đồ thị (đơn, vô hướng) trên $n$ đỉnh. Nếu G không có tam giác thì G không có nhiều hơn $\left[ \dfrac{n^2}{4}\right]$ cạnh. Đẳng thức xảy ra khi và chỉ khi $G=K_{ \frac{n}{2} , \frac{n}{2}}$ nếu $n$ chẵn và $K_{\frac{n-1}{2} , \frac{n+1}{2}}$ nếu $n$ lẻ.
Chứng minh:

Goi I là một tập hợp các đỉnh độc lập (đôi một không có cạnh nối) cực đại và $| I | = x$. J là tập các đỉnh còn lại của G vậy $|J|=n-x$. Ta có các nhận xét sau:
$\bullet$ Mỗi cạnh của G có 1 đầu mút trong I, vì một cạnh nếu có cả 2 đầu mút sẽ khiến I không độc lập.
$\bullet \deg (A) \le x \ \forall A$. Thật vậy, vì G không có tam giác nên với mỗi đỉnh A, 2 đỉnh kề của A không kề nhau. Nói cách khác tập các đỉnh kề A là độc lập. Do ta giả sử $|I|$ là cực đại nên $\deg (A) \le x$.
Như vậy nếu $e$ là số cạnh của G thì $$e \le \sum_{A \in J} \deg (A) \le \sum_{A \in J} x = x(n-x) \le \left [ \dfrac{n^2}{4} \right ] $$

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]