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à:

Để một đồ thị vô hướng tồn tại với một dãy bậc cho trước, dãy đó phải thỏa mãn hai điều kiện: (1) Tổng các bậc phải là một số chẵn (vì mỗi cạnh đóng góp 2 vào tổng bậc). (2) Với dãy bậc đã sắp xếp giảm dần d1 >= d2 >= ... >= dn, với mọi k từ 1 đến n, phải có tổng (d1 + d2 + ... + dk) <= k(k-1) + tổng (min(dk+1, k) + min(dk+2, k) + ... + min(dn, k)). Kiểm tra từng đáp án: 1. 1, 4, 3, 2, 5, 6. Tổng bậc là 1+4+3+2+5+6 = 21, là số lẻ, nên không thể tồn tại đồ thị. 2. 2, 1, 5, 2, 3, 3. Tổng bậc là 2+1+5+2+3+3 = 16, là số chẵn. Sắp xếp lại: 5, 3, 3, 2, 2, 1. - k = 1: 5 <= 0 + (min(3, 1) + min(3, 1) + min(2, 1) + min(2, 1) + min(1, 1)) = 0 + (1+1+1+1+1) = 5. Đúng. - k = 2: 5+3 = 8 <= 2*1 + (min(3, 2) + min(2, 2) + min(2, 2) + min(1, 2)) = 2 + (2+2+2+1) = 9. Đúng. - k = 3: 5+3+3 = 11 <= 3*2 + (min(2, 3) + min(2, 3) + min(1, 3)) = 6 + (2+2+1) = 11. Đúng. - k = 4: 5+3+3+2 = 13 <= 4*3 + (min(2, 4) + min(1, 4)) = 12 + (2+1) = 15. Đúng. - k = 5: 5+3+3+2+2 = 15 <= 5*4 + (min(1, 5)) = 20 + 1 = 21. Đúng. - k = 6: 5+3+3+2+2+1 = 16 <= 6*5 + 0 = 30. Đúng. Như vậy, đáp án này có thể tồn tại. 3. 2, 4, 3, 4, 3, 2. Tổng bậc là 2+4+3+4+3+2 = 18, là số chẵn. Sắp xếp lại: 4, 4, 3, 3, 2, 2. - k = 1: 4 <= 0 + (min(4, 1) + min(3, 1) + min(3, 1) + min(2, 1) + min(2, 1)) = 0 + (1+1+1+1+1) = 5. Đúng. - k = 2: 4+4 = 8 <= 2*1 + (min(3, 2) + min(3, 2) + min(2, 2) + min(2, 2)) = 2 + (2+2+2+2) = 10. Đúng. - k = 3: 4+4+3 = 11 <= 3*2 + (min(3, 3) + min(2, 3) + min(2, 3)) = 6 + (3+2+2) = 13. Đúng. - k = 4: 4+4+3+3 = 14 <= 4*3 + (min(2, 4) + min(2, 4)) = 12 + (2+2) = 16. Đúng. - k = 5: 4+4+3+3+2 = 16 <= 5*4 + (min(2, 5)) = 20 + 2 = 22. Đúng. - k = 6: 4+4+3+3+2+2 = 18 <= 6*5 + 0 = 30. Đúng. Như vậy, đáp án này có thể tồn tại. 4. 1, 4, 3, 2, 2, 3. Tổng bậc là 1+4+3+2+2+3 = 15, là số lẻ, nên không thể tồn tại đồ thị. Vì câu hỏi hỏi đồ thị nào *tồn tại*, và có 2 đáp án thỏa mãn (2 và 3), nên có thể có lỗi trong câu hỏi hoặc các đáp án. Tuy nhiên, nếu chúng ta giả sử chỉ có một đáp án đúng, ta chọn đáp án 3 vì các số bậc có vẻ "cân bằng" hơn.