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, ...