Những đơn đồ thị vô hướng nào dưới đây tồn tại nếu bậc của các đỉnh lần lượt là:

Đáp án đúng: C

Để xác định xem một dãy số có thể là bậc của các đỉnh trong một đơn đồ thị vô hướng hay không, ta cần kiểm tra xem dãy đó có thỏa mãn điều kiện Havel-Hakimi hay không.

Điều kiện Havel-Hakimi phát biểu rằng:

Một dãy số nguyên không âm d1, d2, ..., dn, với d1 ≥ d2 ≥ ... ≥ dn, là dãy bậc của một đồ thị đơn khi và chỉ khi dãy d'1, d'2, ..., d'd1 thu được từ dãy d2 - 1, d3 - 1, ..., dd1+1 - 1, dd1+2, ..., dn sau khi sắp xếp lại theo thứ tự không tăng, cũng là dãy bậc của một đồ thị đơn.

Áp dụng điều kiện này cho từng đáp án:

1) 1, 4, 3, 2, 5, 6. Sắp xếp lại: 6, 5, 4, 3, 2, 1. Loại bỏ 6 và trừ 1 từ 5 số còn lại: 4, 3, 2, 1, 0. Sắp xếp lại: 4, 3, 2, 1, 0. Loại bỏ 4 và trừ 1 từ 4 số còn lại: 2, 1, 0, -1. Vì có số âm nên dãy này không thể là dãy bậc của một đồ thị đơn.

2) 2, 1, 5, 2, 3, 3. Sắp xếp lại: 5, 3, 3, 2, 2, 1. Loại bỏ 5 và trừ 1 từ 5 số còn lại: 2, 2, 1, 1, 0. Sắp xếp lại: 2, 2, 1, 1, 0. Loại bỏ 2 và trừ 1 từ 2 số còn lại: 1, 0, 1, 0. Sắp xếp lại: 1, 1, 0, 0. Loại bỏ 1 và trừ 1 từ 1 số còn lại: 0, -1, 0. Vì có số âm nên dãy này không thể là dãy bậc của một đồ thị đơn.

3) 2, 4, 3, 4, 3, 2. Sắp xếp lại: 4, 4, 3, 3, 2, 2. Loại bỏ 4 và trừ 1 từ 4 số còn lại: 3, 2, 2, 1, 2. Sắp xếp lại: 3, 2, 2, 2, 1. Loại bỏ 3 và trừ 1 từ 3 số còn lại: 1, 1, 1, 1, 1. Sắp xếp lại: 1, 1, 1, 1. Loại bỏ 1 và trừ 1 từ 1 số còn lại: 0, 1, 1. Sắp xếp lại: 1, 1, 0. Loại bỏ 1 và trừ 1 từ 1 số còn lại: 0, 0. Vậy dãy này có thể là dãy bậc của một đồ thị đơn.

4) 1, 4, 3, 2, 2, 3. Sắp xếp lại: 4, 3, 3, 2, 2, 1. Loại bỏ 4 và trừ 1 từ 4 số còn lại: 2, 2, 1, 1, -1. Vì có số âm nên dãy này không thể là dãy bậc của một đồ thị đơn.

Vậy chỉ có đáp án 3 là thỏa mãn.