grahp
 

Trong một buổi dạ hội, mỗi người tham dự đều có ít nhất 3 người bạn, cmr có thể chọn ra 1 số chẵn người để xếp ngồi quanh một bàn tròn sao cho mỗi người đều ngồi giữa 2 người quen.

Bài toán tổng quát của bài toán này là:

Trong một đồ thị mà có $\ge \frac{3n}{2} $ cạnh thì có ít nhất một chu kì độ dài chẵn. Dùng nó có thể giải được bài graph của VMEO III.

Chứng minh:

Trước hết ta chỉ cần chứng minh cho đồ thị liên thông.

Nhận xét 1: Nếu có hai chu trình có chung cạnh thì tồn tại chu trình chẵn.

Nhận xét 2: Từ một cây, thêm một cạnh bất kì thì có thêm một chu trình.

Giả sử T là cây cơ bản của đồ thị G, Giả sử G không có chu trình đồ dài chẵn. Ta có khi thêm cho T một cạnh bất kì thì số chu trình trong G tăng lên 1, mà ta có không có 2 chu trình nào có chung cạnh và mỗi chu trình có độ dài ít nhất là 3, do đó số cạnh thêm vào không lớn hơn $n-1/2 $, hay tổng số cạnh của đồ thị không lớn hơn $3(n-1)/2 $