双连通图 -- 来自 Wolfram MathWorld

双连通图是一个连通图，它没有割点（Skiena 1990, p. 175）。对于顶点数多于两个的图，一个等价的定义是图的顶点连通度。

顶点数为 , 2, ... 的双连通简单图的数量分别是 0, 0, 1, 3, 10, 56, 468, ... （参见 OEIS A002218）。上面展示了这些图的前几个。

顶点数大于等于 2 的极大连通图被称为块或不可分图（参见 Harary 1994, p. 26）。双连通图与块密切相关。如果一个块的顶点数多于两个，那么它是双连通的（West 2000, p. 155）。反之，顶点数大于等于 2 的双连通图是块。

上面展示了一些连通但不双连通的图。这样的图被称为 1-连通图，顶点数为 , 2, ... 的 1-连通图的数量分别为 1, 1, 1, 3, 11, 56, 385, ... （OEIS A052442）。

可以使用 Wolfram 语言测试图的双连通性，使用KVertexConnectedGraphQ[g, 2] 或VertexConnectivity[g] 。可以使用以下命令获取双连通图的集合GraphData["Biconnected].

任何包含度为 1 的节点的图都不可能是双连通的。所有哈密顿图都是双连通的（Skiena 1990, p. 177），但反之不一定成立。特别是，非双连通图自动是非哈密顿图，这可以通过注意到如果删除一个割点后留下哈密顿路径，这将意味着不连通的图是连通的。下表总结了一些双连通但非哈密顿的命名图。

双连通图