k-連通圖

如果一個圖 頂點數多於兩個，則稱其為 -連通的（或 -頂點連通，或 -點連通），如果不存在大小為 的頂點割，移除該頂點割會使圖斷開連線，即如果頂點連通度 。 因此，頂點數多於一個的連通圖是 1-連通的，而頂點數多於兩個的雙連通圖是 2-連通的。

單點圖是“令人惱火地不一致的”（West 2000，第 150 頁），因為它已連線（特別是 1-連通），但按照慣例，它被認為具有 。

輪圖是“基本的 3-連通圖”（Tutte 1961；Skiena 1990，第 179 頁）。

-連通性圖檢查在 Wolfram 語言中實現為KVertexConnectedGraphQ[g, k].

下表給出了 -連通圖的數量，針對 -節點圖（將單點圖 算作 1-連通，將路徑圖 算作 2-連通）。

	OEIS	-連通圖，節點數為 1, 2, ...
1	A001349	1, 1, 2, 6, 21, 112, 853, 11117, 261080, ...
2	A002218	0, 1, 1, 3, 10, 56, 468, 7123, 194066, ...
3	A006290	0, 0, 0, 1, 3, 17, 136, 2388, 80890, ...
4	A086216	0, 0, 0, 0, 1, 4, 25, 384, 14480, ...
5	A086217	0, 0, 0, 0, 0, 1, 4, 39, 1051, 102630, 22331311, ...
6	A324240	0, 0, 0, 0, 0, 0, 1, 5, 59, 3211, 830896, ...
7	A324092	0, 0, 0, 0, 0, 0, 0, 1, 5, 87, 9940, 7532629, ...