关于连通立方图中是否存在仅含一个Tutte桥的圈的技术问询

嘿，这个问题挺有讨论价值的！先帮你把涉及的定义再明确一遍，避免混淆：

给定连通立方图 $G$ 和 $G$ 中的圈 $C$，$(G,C)$ 的Tutte桥是图 $G-E(C)$（即去掉圈 $C$ 的所有边之后的图）的连通分支。

接下来直接说结论：答案是否定的——并不是所有连通立方图都存在这样的圈，最经典的反例就是彼得森图（Petersen graph）。

彼得森图是3-正则（立方）、连通的图，它有个关键特性：它是无哈密顿圈的亚哈密顿图（本身没有哈密顿圈，但去掉任意一个顶点后就存在哈密顿圈）。咱们拆解它的情况：

• 如果取彼得森图里的任意非哈密顿圈（它的最长圈是8-圈），去掉这个圈的边之后，剩下的子图会至少包含两个连通分支，也就是至少两个Tutte桥；
• 退一步说，就算假设它存在哈密顿圈（实际并不存在），去掉哈密顿圈的边后，剩下的是一个完美匹配（每个顶点还剩一条未用的边），这时候会有5个孤立边作为连通分支，显然也远不止一个Tutte桥。

除了彼得森图，还有一些亚哈密顿立方图也具备这个性质：它们的任何圈都无法让去掉圈边后的子图仅存在一个连通分支。

备注：内容来源于stack exchange，提问作者gotcha game