设 是连通图
的一个边割。那么循环边连通性
是最小循环边割的大小,即最小的边割
,使得
有两个连通分量,且每个连通分量都至少包含一个图的环。循环边连通性最早由 Tait (1880) 在 1880 年提出。
注意 Grünbaum (2003, p. 365) 和其他人使用术语“循环 -连通”(省略了“边”字)来指一个图,它不能通过少于
条边的边割被分成两个独立的部分,且每个部分都包含一个环。
循环边割并非对所有图都存在。例如,包含少于两个环的图不可能有两个都包含环的连通分量。没有循环边割的图的例子包括轮图 (Dvorák et al. 2004)。对于不存在循环边割的图,可以认为其
(Lou et al. 2001)。
Petersen 图的循环边连通性是 (Holton and Sheehan 1993, p. 86; Lou et al. 2001)。这可以从移除五条“径向”边后,留下一个不连通的内部五角星环和外部五边形环这一事实看出。
循环边连通性最常在 snark 图的定义中遇到,snark 图被定义为围长至少为 5 且边色数为 4 的三次循环 4-边连通图。
Birkhoff (1913) 将四色问题简化为循环 5-边连通的多面体图 (Grünbaum 2003, p. 365)。Hunter (1962) 推测这样的图都是 Hamiltonian 图,但这一推测被 162 顶点的三次非 Hamiltonian 162 顶点 Walther 图的发现所驳斥 (Walther 1965, Grünbaum 2003, p. 365)。
Plummer (1972) 表明,平面 5-连通图的循环边连通性最多为 13,而平面 4-连通图的循环边连通性可以是任何大于等于 4 的整数值。Borodin (1989) 表明,平面 5-连通图的最大循环边连通性最多为 11。
一个具有 个节点的简单图的循环边连通性满足
当 时,完全图等号成立,即当
时,
(Lou et al. 2001)。