K-liên thông

Đồ thị G được gọi là k - liên thông (tiếng Anh: k-connected) hay đầy đủ hơn là k - đỉnh liên thông (tiếng Anh: k-vertex-connected) nếu ta xóa đi không quá k-1 đỉnh bất kì và các cạnh liên thuộc với các đỉnh đó thì đồ thị còn lại vẫn liên thông^[1].

Nhận xét:

Mọi đồ thị (không rỗng) đều là 0 - liên thông.
Mọi đồ thị liên thông đều là 1 - liên thông.
Đồ thị đầy đủ $K_{n}$ là (n-1) - liên thông.
Một đồ thị là k - liên thông thì cũng là h - liên thông với h<k, 0<k.

Số k lớn nhất sao cho G là k - liên thông được gọi là độ liên thông (tiếng Anh: connectivity), ký hiệu là κ(G)^[1].

Ví dụ:

Khi xóa 3 đỉnh bất kì của H và các cạnh liên thuộc với chúng, đồ thị còn lại vẫn liên thông.
Nếu ta xóa đi 4 đỉnh màu đỏ thì đồ thị còn lại không liên thông nữa.

Đồ thị H trong hình vẽ có 6 đỉnh, nếu ta xóa đi 3 đỉnh bất kì và các cạnh liên thuộc với chúng, đồ thị còn lại vẫn liên thông, do đó H là 3 - liên thông, và tất nhiên cũng là 2 - liên thông và 1 - liên thông. Nếu như ta xóa 4 đỉnh màu đỏ thì đồ thị không còn liên thông nữa, do đó κ(H) = 4.