Cho đồ thị vô hướng trọng số trên cạnh G = (V, E) trong đó V = {1,2,3,4,5,6} và E = {(1,2),(1,3),(1,6),(2,3),(2,5),(2,6),(4,5),(4,6),(5,6)}. Trọng số trên cạnh w(1,2) = 1, w(1,3) = 1, w(1,6) = 4, w(2,3) = 1, w(2,5) = 2, w(2,6) = 2, w(4,5) = 3, w(4,6) = 5, w(5,6) = 2. Hỏi có tồn tại cây khung nhỏ nhất của G chứa cạnh (4,6) hay không?

Để xét xem một đồ thị phẳng liên thông có tồn tại hay không, ta sử dụng công thức Euler cho đồ thị phẳng liên thông: v - e + f = 2, trong đó v là số đỉnh, e là số cạnh, và f là số mặt. Ngoài ra, ta có bất đẳng thức 3f ≤ 2e (mỗi mặt được bao bởi ít nhất 3 cạnh, và mỗi cạnh thuộc nhiều nhất 2 mặt). Điều này chỉ đúng khi đồ thị không có cạnh song song và khuyên. Thay f = 2 - v + e vào bất đẳng thức trên, ta được: 3(2 - v + e) ≤ 2e => 6 - 3v + 3e ≤ 2e => e ≤ 3v - 6. Trong trường hợp này, v = 6 và e = 14. Thay vào bất đẳng thức, ta có: 14 ≤ 3(6) - 6 => 14 ≤ 18 - 6 => 14 ≤ 12. Bất đẳng thức này sai, vậy không tồn tại đồ thị phẳng liên thông với 6 đỉnh và 14 cạnh.

Để giải bài toán này, ta sẽ xét các trường hợp có ít nhất hai số liên tiếp nhau được chọn trong 4 số được chọn từ tập {1, 2, 3, 4, 5, 6, 7}.

Gọi A là tập các bộ 4 số được chọn từ {1, 2, 3, 4, 5, 6, 7}.

Trường hợp 1: Có đúng một cặp số liên tiếp.
Ví dụ: {1, 2, 4, 6}

Trường hợp 2: Có hai cặp số liên tiếp.
Ví dụ: {1, 2, 3, 5} hoặc {1, 2, 6, 7}

Trường hợp 3: Có ba số liên tiếp.
Ví dụ: {1, 2, 3, 5}

Trường hợp 4: Có bốn số liên tiếp.
Ví dụ: {1, 2, 3, 4}

Ta sẽ sử dụng phương pháp phần bù. Tính tổng số cách chọn 4 số bất kỳ từ 7 số, sau đó trừ đi số cách chọn 4 số mà không có hai số nào liên tiếp.

Tổng số cách chọn 4 số từ 7 số là C(7, 4) = 7! / (4! * 3!) = (7 * 6 * 5) / (3 * 2 * 1) = 35.

Bây giờ ta tính số cách chọn 4 số từ 7 số sao cho không có hai số nào liên tiếp.
Gọi x1, x2, x3, x4 là 4 số được chọn, sao cho 1 <= x1 < x2 < x3 < x4 <= 7.
Để không có hai số nào liên tiếp, ta có x2 >= x1 + 2, x3 >= x2 + 2, x4 >= x3 + 2.
Đặt y1 = x1, y2 = x2 - 1, y3 = x3 - 2, y4 = x4 - 3.
Khi đó 1 <= y1 < y2 < y3 < y4 <= 4.
Số cách chọn 4 số y1, y2, y3, y4 từ tập {1, 2, 3, 4} là C(4, 4) = 1.
Vì vậy, số cách chọn 4 số từ 7 số sao cho không có hai số nào liên tiếp là C(7 - 4 + 1, 4) = C(4, 4) = 1. C(7-4+1, 4) = C(4,4) = 1.
Vậy số cách chọn 4 số từ 7 số sao cho không có hai số nào liên tiếp là C(4,4) = 1.
Vậy số cách chọn 4 số từ 7 số sao cho không có hai số nào liên tiếp là C(7-3,4) = C(4,4) = 1 cách.
Số cách chọn 4 số từ 7 số sao cho không có 2 số nào liên tiếp là: C(n-k+1, k) = C(7-4+1, 4) = C(4, 4) = 1.
Số cách chọn 4 số từ 7 số sao cho không có 2 số nào liên tiếp là 1.

Số cách chọn ra 4 phần tử từ 7 số 1, 2, …, 7 sao cho luôn có 2 số liên tiếp nhau cùng được chọn là: 35 - 1 = 34.

Vậy đáp án đúng là 34.