Chứng minh rằng nếu $G$ là đồ thị đơn phân đôi có $v$ đỉnh và $e$ cạnh khi đó $e\le \frac{v^2}{4}$.

Chứng minh rằng nếu $G$ là đồ thị đơn phân đôi có $v$ đỉnh và $e$ cạnh khi đó $e\le \frac{v^2}{4}$.

Giải

G/s đơn đồ thị lưỡng phân $G$ có tập đỉnh được chia thành hai tập con $X,Y$ với $|X|=m,\ |Y|=n$. Ta có $m+n=v$.

Ứng với mỗi đỉnh $x_i\in X\ (i=\overline{1,m})$ thì ta có số cạnh của đồ thị mà nối với $x_i$ là $e_{x_i}\le n$ (do từ $x_i$ chỉ có thể nối tối đa với $n$ đỉnh trong $Y$).

Do đó : $e=\sum_{i=1}^{m}e_{x_i}\le\sum_{i=1}^{m}n=m.n\overset{Côsi}{\le}\left(\frac{m+n}{2}\right)^2=\frac{v^2}{4}$. (đpcm)

Dấu $"="\Leftrightarrow G$ là đồ thị lưỡng phân đầy đủ.

Mở rộng : Một $graph$ $v$ đỉnh không chứa tam giác thì số cạnh $e \leq [\frac{v^2}{4}]$