Đồ thị G vô hướng được gọi là liên thông nếu giữa mọi cặp đỉnh u,v bất kỳ đều có:

Một cạnh nối giữa u và v

Một đường đi có hướng nối u đến v

Một đường đi vô hướng nối u đến v

Hai cạnh nối u đến v