Bài tập sưu tầm

Có tồn tại đồ thị hai phía gồm \(16\) đỉnh và \(65\) cạnh không?

Giải

Gọi \(v_1\) là số đỉnh ở đồ thị bên trái và \(v_2\) là số đỉnh ở đồ thị bên phải. Khi đó \(v_1 + v_2 = 16\).

Theo bất đẳng thức AM-GM thì

\[v_1 v_2 \leqslant \frac{(v_1 + v_2)^2}{4} = 64,\]

nhưng \(v_1 v_2\) là số cạnh tối đa mà đồ thị hai phía có thể có, nên không thể đạt tới \(65\) cạnh.

Đáp án: không tồn tại.