次三次无三角形非二部图并不总允许余图连通分支阶数至多为3的独立划分
low tier2026-11-05OP-1087审阅: CodexEnglish
摘要
在次三次图(subcubic graph)的图划分与割问题的研究中,arXiv:2611.05178 的问题 5.4 询问:是否每个最大度至多为 3 且奇围长恰好为 5 的有限简单图都允许将其顶点集划分为不相交子集 $L$ 与 $R$,使得 $L$ 是独立集且 $R$ 上的诱导子图的每个连通分支的阶数至多为 3。该问题得到了否定的回答。一个反例已在 Lean 4 中形式化并经过机械验证,对应定理 subcubic_odd_girth_five_partition_component_le_three_negation。该反例具有顶点 $0,\ldots,7$,边连接模 8 相邻的顶点以及相距为 4 的顶点。它是三次图且无三角形,并且 $0,1,2,3,4,0$ 是一个 5-圈,因此其奇围长恰好为 5。通过证明每个独立集 $L$ 都会留下至少一个顶点,其在补诱导子图中的可达分支阶数超过 3,从而推翻了该全称主张。该结果划定了稀疏图中缺陷顶点划分(defective vertex partition)的界限,与始终存在此类划分的二部图情形形成了对比。
1. 引言
在各部分具有结构约束的图划分问题构成了结构图论与组合优化研究的核心领域。一个常见的目标是将图 $G$ 的顶点集 $V(G)$ 划分为两个不相交的类别 $V(G) = L \cup R$,使得集合 $L$ 是独立集(不诱导任何边),而互补诱导子图 $G[R]$ 满足受控的结构条件,例如具有有界的最大度、有界的退化度或有界的连通分支大小。此类划分推广了正常顶点着色,并与最大割(Max Cut)问题紧密相关,在最大割问题中,人们寻求大型二部子图或将稠密子图隔离为小规模、易处理部分的分解。
在题为“Weighted Max Cut in Subcubic Graphs”的 arXiv:2611.05178 中,研究了次三次图(即最大度至多为 3 的图)类中的结构分解与割性质。在该工作的第 5 节中,问题 5.4 提出了如下公开问题:是否每个奇围长恰好为 5 的次三次图 $G$ 都允许划分 $V(G) = L \cup R$,使得 $L$ 是独立集且 $G[R]$ 的每个分支的阶数至多为 3?
$G$ 的奇围长恰好为 5 这一条件意味着 $G$ 中最短奇圈的长度恰好是 5。等价地,$G$ 不包含长度为 3 的圈(即它是无三角形的),并且包含至少一个长度为 5 的圈,这尤其意味着 $G$ 不是二部图(因为二部图根本不包含奇圈)。对次三次图的限制提供了一个稀疏体系,其中独立集与诱导路径或树已被广泛研究。要求 $G[R]$ 的每个连通分支的阶数至多为 3 是一个很强的有界性要求:它迫使 $G[R]$ 是孤立顶点、孤立边($K_2$)、长为 2 的路径($P_3$)或三角形($K_3$)的不相交并,尽管三角形已经被围长要求所排除。
在这项工作之前,已经理解了若干基线情况。在二部图背景下,答案显然是肯定的:每个二部图都允许 2-着色 $V(G) = V_1 \cup V_2$,其中 $V_1$ 和 $V_2$ 都是独立集。令 $L = V_1$ 则留下 $R = V_2$,在其中每个连通分支都是阶数为 1 的孤立顶点,完全在界限 3 之内。这一事实已在 Lean 中以定理名称 subcubic_partition_component_le_three_of_isBipartite 得到了形式化验证。此外,对于顶点数至多为 3 的平凡小图,独立集的任何选择(包括空集)都会留下总大小至多为 3 的补集,从而保证 $G[R]$ 的每个分支的阶数至多为 3,这一性质在 subcubic_partition_component_le_three_of_card_le_three 中得到了验证。
因此,arXiv:2611.05178 中的问题 5.4 询问的是,在无三角形次三次图中存在 5-圈是否总能通过选择一个独立集 $L$ 来容纳,该独立集将图的剩余部分粉碎为阶数至多为 3 的分支。
本文介绍了对问题 5.4 的形式化反驳。我们报告了定理 subcubic_odd_girth_five_partition_component_le_three_negation,该定理证明了该全称陈述是错误的。具体而言,存在一个有限简单图,其最大度至多为 3、3 阶无团且不是二部图,但却不允许任何独立集使得其补集仅由阶数至多为 3 的分支组成。形式化证明使用了 $\mathbb Z/8\mathbb Z$ 上的图,其对每个 $i$ 都有边 $\{i,i+1\}$ 和 $\{i,i+4\}$。它验证了度数与三角形条件,并检查了每个独立集都在补集中留下阶数至少为 4 的连通分支。圈 $0,1,2,3,4,0$ 直接表明这个特定图的奇围长为 5。
2. 预备知识
我们在 Lean 4 中形式化的有限简单图框架下工作。在本文中,设 $V$ 为配备了可判定相等性的有限类型。
定义 1(简单图,SimpleGraph)。顶点类型 $V$ 上的简单图 $G$ 由对称且反自反的二元关系 $G.\mathrm{Adj} : V \to V \to \mathrm{Prop}$ 组成。对称性意味着对所有 $u, v \in V$,$G.\mathrm{Adj}(u, v) \leftrightarrow G.\mathrm{Adj}(v, u)$,反自反性意味着对所有 $u \in V$,$\neg G.\mathrm{Adj}(u, u)$。在 Lean 中,该关系被假定为可判定的。
定义 2(最大度,SimpleGraph.maxDegree)。对于有限简单图 $G$,顶点 $v \in V$ 的度是其邻点集的基数,$\deg(v) = |\{ u \in V \mid G.\mathrm{Adj}(v, u) \}|$。$G$ 的最大度记作 $\Delta(G)$ 或 SimpleGraph.maxDegree,是所有 $v \in V$ 上 $\deg(v)$ 的最大值。若 $\Delta(G) \le 3$,则称图是次三次的。 *注记。* 在 Lean 中,该条件被形式化为弱不等式 $\Delta(G) \le 3$,允许最大度严格小于 3 的图以及达到度 3 的图。
定义 3(无团图,SimpleGraph.CliqueFree)。对于自然数 $n$,如果 $V$ 中不存在两两相邻的 $n$ 个顶点的子集,则图 $G$ 称为 $n$ 阶无团的,记作 SimpleGraph.CliqueFree。对于 $n = 3$,3 阶 SimpleGraph.CliqueFree 表示 $G$ 不包含 3-团,即 $G$ 是无三角形的。 *注记。* 该条件禁止同构于 $K_3$ 的完全子图。它并不阻止长度为 5 或更大的圈。
定义 4(二部图,SimpleGraph.IsBipartite)。如果存在顶点的 2-着色使得没有两个相邻顶点共享相同的颜色,则图 $G$ 是二部图,记作 SimpleGraph.IsBipartite。图具有奇圈当且仅当它不是二部图。 *注记。* 同时满足 3 阶 SimpleGraph.CliqueFree 与 SimpleGraph.IsBipartite 之否定的图不可能含有长度为 3 的奇圈,因此其最短奇圈的长度必须至少为 5。当图包含 5-圈时,其奇围长恰好为 5。
定义 5(诱导子图,SimpleGraph.induce)。给定顶点子集 $S \subseteq V$,在 Lean 中形式化为 SimpleGraph.induce 的诱导子图 $G[S]$ 是以子类型 $\{ v : V // v \in S \}$ 为顶点类型的简单图,其中两个顶点 $\langle u, h_u \rangle$ 与 $\langle v, h_v \rangle$ 相邻当且仅当 $G.\mathrm{Adj}(u, v)$。
定义 6(独立集)。如果 $L$ 中没有两个不同的顶点相邻,则子集 $L \subseteq V$ 是 $G$ 的独立集。在 Lean 中,这在代数上由在 $L$ 上的 SimpleGraph.induce 等于空图 $\bot$($L$ 上简单图格的底元素)的等式来表示。这等价于陈述:对所有 $x, y \in L$ 且 $x \neq y$,$\neg G.\mathrm{Adj}(x, y)$。
定义 7(连通分支与阶数,SimpleGraph.ConnectedComponent)。如果在图 $H$ 中存在从 $u$ 到 $v$ 的途径(walk),则 $H$ 中的两个顶点 $u, v$ 是相互可达的。$H$ 的连通分支是可达性关系的等价类,由商类型 SimpleGraph.ConnectedComponent 表示。对于 $L$ 的补集上的诱导子图,分支是 $G[L^c]$ 的连通分支。分支 $C$ 的阶数是其基数,记作 $|C|$。 *注记。* 在 Lean 中,分支大小可以用有限类型基数或一般的自然数基数来度量,标准库的等价引理建立了它们之间的联系。补图中每个连通分支的阶数至多为 3 这一条件是通过对所有分支 $C$ 的全称量词编写的,要求 $C$ 的基数至多为 3。
定义 8(可达分支子图)。给定独立集 $L$ 与顶点 $v \in L^c$,$v$ 在 $G[L^c]$ 中的连通分支可以表示为从 $v$ 可达的所有顶点的有限集(finset): $$S = \{ w \in L^c \mid (G[L^c]).\mathrm{Reachable}(v, w) \}$$ 在 Lean 中,该有限集是通过在全顶点集上过滤出 $v$ 和 $w$ 在补诱导子图中由路径相连这一条件来构造的。
3. 主要结果
Lean 证明中的反例反驳了来自 arXiv:2611.05178 的问题 5.4。其定理针对更广泛的无三角形、非二部次三次图类陈述;这些条件本身仅蕴涵奇围长至少为 5。对于证明中使用的特定图,下文展示的 5-圈使其奇围长恰好为 5。
定理(subcubic_odd_girth_five_partition_component_le_three_negation)。并非每个最大度 $\Delta(G) \le 3$、3 阶无团且不是二部图的有限简单图 $G = (V, E)$ 都允许将其顶点集划分为独立集 $L$ 与补集 $R = L^c$,使得诱导子图 $G[R]$ 的每个连通分支的阶数至多为 3: $$\neg \Big( \forall (V, G), \Delta(G) \le 3 \land G.\mathrm{CliqueFree}(3) \land \neg G.\mathrm{IsBipartite} \implies \exists L \subseteq V, G[L] = \emptyset \land \forall C \in \pi_0(G[L^c]), |C| \le 3 \Big)$$
在 Lean 中,该定理形式化为关于所有具有可判定相等性的有限类型 $V$ 以及 $V$ 上具有可判定邻接关系的简单图 $G$ 的全称命题之否定,即否定:在 SimpleGraph.maxDegree 至多为 3、3 阶 SimpleGraph.CliqueFree 以及 SimpleGraph.IsBipartite 的否定的假设下,存在表示 $L$ 的有限集使得在 $L$ 上的 SimpleGraph.induce 为空,且补图的每个 SimpleGraph.ConnectedComponent 的基数至多为 3。
除了这一反驳之外,更早的形式化还为相关图族建立了正面结论,从而阐明了该问题的范围:
- 二部图(subcubic_partition_component_le_three_of_isBipartite)。每个二部有限简单图都允许将其顶点集划分为独立集 $L$ 与补集 $R = L^c$,使得诱导子图 $G[R]$ 的每个连通分支的阶数至多为 3。 该定理表明,主定理中所确立的失效要求非二部性:在任何二部图中,顶点集都可以划分为两个独立集 $V_1$ 和 $V_2$,因此取 $L = V_1$ 可以保证 $G[R] = G[V_2]$ 的每个分支都是阶数为 1 的孤立顶点,这严格满足了界限 3。
- 小图(subcubic_partition_component_le_three_of_card_le_three)。至多有 3 个顶点的每个有限简单图都允许将其顶点集划分为独立集 $L$ 与补集 $R = L^c$,使得诱导子图 $G[R]$ 的每个连通分支的阶数至多为 3。 该结果证实了任何反例的阶数必须严格大于 3。对于任何满足 $|V| \le 3$ 的图,选取 $L = \emptyset$ 会留下 $|R| \le 3$,确保无论边的结构或二部性如何,没有任何分支可能超过阶数 3。
这些正面情形将反例定位于二部图类之外,并显示出任何反例阶数上四个顶点的初等下界。
theorem subcubic_odd_girth_five_partition_component_le_three_negation : ¬ (∀ {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj], G.maxDegree ≤ 3 → G.CliqueFree 3 → ¬G.IsBipartite → ∃ L : Finset V, G.induce (L : Set V) = ⊥ ∧ ∀ C : (G.induce (Lᶜ : Set V)).ConnectedComponent, open scoped Classical in Fintype.card C ≤ 3)
4. 证明
我们首先介绍证明的总体思路,然后陈述并证明中间引理,最后将它们组合成与 Lean 形式化相匹配的完整论证。
subcubic_odd_girth_five_partition_component_le_three_negation 的证明采用反证法。假设全称主张成立,我们将其记为 $H$: $$H : \forall \{V : \mathrm{Type}^*\} [ \mathrm{Fintype}\ V ] [ \mathrm{DecidableEq}\ V ] (G : \mathrm{SimpleGraph}\ V) [ \mathrm{DecidableRel}\ G.\mathrm{Adj} ],$$ $$G.\mathrm{maxDegree} \le 3 \to G.\mathrm{CliqueFree}\ 3 \to \neg G.\mathrm{IsBipartite} \to \exists L : \mathrm{Finset}\ V, G.\mathrm{induce}(L) = \bot \land \forall C, |C| \le 3$$ 我们用 $\mathbb Z/8\mathbb Z$ 上的八顶点图 $G_0$ 来实例化 $H$,$G_0$ 的边对所有 $i$ 为 $\{i,i+1\}$ 和 $\{i,i+4\}$,运算为模 8 算术。每个顶点具有邻点 $i-1,i+1,i+4$。圈 $0,1,2,3,4,0$ 的长度为 5;连同下文的无三角形性,它证明了奇围长恰好为 5。为了将 $H$ 应用于 $G_0$,形式化证明通过下文的引理 1、2 和 3 验证了三个前提条件。
引理 1(最大度界限)。反例图 $G_0$ 的最大度至多为 3。 *证明。* 在 Lean 中,最大度被定义为有限顶点集 $V$ 上顶点度的上确界。对于每个顶点 $v \in V$,其邻域 $\{ u \in V \mid G_0.\mathrm{Adj}(v, u) \}$ 的基数是通过计算求值的。由于每个顶点的邻域大小至多为 3,因此最大度满足 $\Delta(G_0) \le 3$。
引理 2(无三角形)。反例图 $G_0$ 是 3 阶无团的(3 阶 SimpleGraph.CliqueFree)。 *证明。* 如果不存在两两相互相邻的 3 个顶点的集合,则图是 3 阶无团的。Lean 通过穷举检查顶点集的所有 3 元子集来确定这一性质。对于每组三元顶点 $\{u, v, w\}$,可判定的邻接关系验证了至少有一对是不相邻的。因此图中不存在三角形。
引理 3(非二部性)。反例图 $G_0$ 不是二部图(SimpleGraph.IsBipartite 的否定)。 *证明。* 二部性等价于 2-可着色性。Lean 通过有限计算检查出,将两种颜色分配给这八个顶点的每种分配方式都会使某对相邻顶点获得相同的颜色。这与正常 2-着色相矛盾。独立地,所展示的 5-圈使非二部性与确切的奇围长清晰可见。
在建立了这三个引理之后,用 $G_0$ 实例化 $H$ 会给出一个顶点的有限子集 $L$ 以及两个假设:
- $h_{\mathrm{ind}} : G_0.\mathrm{induce}(L) = \bot$,断言 $L$ 是独立集。
- $h_{\mathrm{comp}} : \forall C : (G_0.\mathrm{induce}(L^c)).\mathrm{ConnectedComponent}, |C| \le 3$,断言补图的每个连通分支的基数至多为 3。
为了使独立性条件在计算上可用,证明提取了两两不相邻性:
引理 4(两两不相邻性)。设 $L$ 为顶点的有限集,满足在 $L$ 上的 SimpleGraph.induce 等于 $\bot$。则对所有 $x \in L$ 和 $y \in L$ 且 $x \neq y$,$\neg G_0.\mathrm{Adj}(x, y)$。 *证明。* 设 $x, y \in L$ 且 $x \neq y$,反设 $G_0.\mathrm{Adj}(x, y)$。根据诱导子图中邻接关系的定义,对应的子类型元素 $\langle x, h_x \rangle$ 与 $\langle y, h_y \rangle$ 在 $L$ 上的诱导子图中相邻。代入 $h_{\mathrm{ind}}$,这意味着这些顶点在 $\bot$ 中相邻。然而,空图 $\bot$ 不包含任何相邻顶点对,从而导出矛盾。因此 $x$ 与 $y$ 不能相邻。我们将该两两不相邻条件记作 $h_L$。
接下来,证明依赖于图 $G_0$ 的一个关键结构性质:
引理 5(小分支的障碍)。对于满足两两不相邻条件 $h_L$ 的 $G_0$ 的任意顶点子集 $L$,在补集 $L^c$ 中存在一个满足可达性障碍性质 $h_v$ 的顶点 $v \in V$。 *证明。* Lean 通过 decide 证明了这个有限断言:对于全部 $2^8$ 个子集中的每一个,如果该子集是独立的,它会检查补集中的某个顶点在补集中至少有四个可达顶点。该引理返回这样一个顶点和相应的基数界限。这是对所述障碍的穷举验证,而不是对独立集的分类。
引理 6(基数矛盾)。设 $G_0$ 为反例图,设 $L \subseteq V$,且设 $v \in L^c$ 为满足障碍性质 $h_v$ 的顶点。定义可达集: $$S = \{ w \in L^c \mid (G_0[L^c]).\mathrm{Reachable}(v, w) \}$$ 如果 $G_0[L^c]$ 的每个连通分支 $C$ 都满足 $|C| \le 3$,则导出矛盾。 *证明。* 根据构造,$S$ 恰好是在诱导子图 $G_0[L^c]$ 中包含 $v$ 的连通分支的顶点集。条件 $h_v$ 确保 $S$ 至少包含 4 个不同的顶点。在 Lean 中,对应于 $v$ 的分支被识别为补图连通分支的商类型的一个元素。所有分支基数至多为 3 的假设迫使 $|C| \le 3$,这与 $S$ 中存在至少 4 个可达顶点相矛盾。该引理形式化了这一算术矛盾并导出了矛盾。
组合各步骤: subcubic_odd_girth_five_partition_component_le_three_negation 的证明按如下顺序将这些部分组合在一起: 1. 通过引入假设 $H$。 2. 将 $H$ 应用于 $G_0$,提供引理 1(最大度界限)、引理 2(无三角形)和引理 3(非二部性)。 3. 获得独立有限集 $L$、等式 $h_{\mathrm{ind}} : G_0.\mathrm{induce}(L) = \bot$ 以及分支界限 $h_{\mathrm{comp}} : \forall C, |C| \le 3$。 4. 从 $h_{\mathrm{ind}}$ 出发,通过引理 4 构造 $h_L$,表明 $L$ 不包含相邻顶点对。 5. 将引理 5 应用于 $L$ 和 $h_L$,以获得见证顶点 $v$ 和证明 $h_v$。 6. 将分支基数界限转换为自然数基数,产生 $h_{\mathrm{comp}}' : \forall C, |C| \le 3$。 7. 通过在顶点集上过滤出在 $L^c$ 上的诱导子图中从 $v$ 可达的元素来定义 $S$。 8. 将引理 6 应用于 $G_0$、$L^c$、$v$、$S$、$h_v$、过滤成员关系刻画以及 $h_{\mathrm{comp}}'$。 9. 所得到的矛盾完成了反驳。
5. 讨论
定理 subcubic_odd_girth_five_partition_component_le_three_negation 对 arXiv:2611.05178 的问题 5.4 给出了否定的回答。它确立了奇围长为 5 的次三次图并不总允许划分为一个独立集和一个各分支阶数至多为 3 的诱导子图。
考察该结果如何相对于具有分支阶数约束的图划分更广泛理论定位自身是很有启发性的:
1. 与二部图的对比。如 subcubic_partition_component_le_three_of_isBipartite 所记录,二部图无条件地允许此类分支阶数至多为 1 的划分(因为划分的两个类都是独立集)。在二部图中不存在奇圈,这意味着色数为 2。arXiv:2611.05178 中提出的问题试图确定,允许最短奇圈长度为 5 是否可以通过轻微放宽——从独立分支(阶数为 1)到阶数至多为 3 的分支——来吸收非二部性障碍。八顶点反例证明了阶数 3 对于此类图是不够的;形式化证明通过有限检查确立了该障碍。
2. 分支阶数阈值。这一反驳引发的一个自然后续问题是,关于分支阶数是否存在更大的常数界限。也就是说,是否存在整数 $k \ge 4$,使得每个奇围长为 5 的次三次图都允许划分 $V = L \cup R$,其中 $L$ 为独立集且 $G[R]$ 的每个分支的阶数至多为 $k$?如果不存在这样的普遍常数 $k$,人们会想确定 $G[R]$ 中的最大分支阶数是否会随着顶点数任意增大,或者它是否可以作为诸如树宽(treewidth)或最大度等图不变量的函数来界定。
3. 更高的奇围长。另一个方向涉及加强围长假设。问题 5.4 特别将奇围长固定为恰好 5。对于奇围长为 7、9 或更大的次三次图,情况会如何?增加奇围长排除了短奇圈,尽管偶圈仍可能出现。是否存在一个奇围长阈值 $g_{\mathrm{odd}} \ge 7$,超过该阈值后每个次三次图都允许余图分支阶数至多为 3 的独立集,抑或该反例构造可以推广到更高的奇围长?
4. 算法与割意义。在 arXiv:2611.05178 研究的带权最大割问题的背景下,具有小分支的独立补集划分为分治策略与近似算法提供了结构工具。分支阶数至多为 3 的划分的不存在表明,依赖此类划分的算法设计必须要么容忍阶数为 4 或更大的分支,要么利用替代的结构分解。
为什么是研究级成果
- refutes OP-1087 (Partition of Odd-Girth 5 Subcubic Graphs with Component Order at Most Three)
Lean 声明
- subcubic_odd_girth_five_partition_component_le_three_negationIt is not the case that every finite simple graph with maximum degree at most 3, clique-free of order 3, and not bipartite admits a…
- subcubic_partition_component_le_three_of_isBipartiteEvery bipartite finite simple graph admits a partition of its vertex set into an independent set L and a complement R = Lᶜ such that every…
- subcubic_partition_component_le_three_of_card_le_threeEvery finite simple graph on at most 3 vertices admits a partition of its vertex set into an independent set L and a complement R = Lᶜ…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2611.05178 — Weighted Max Cut in Subcubic Graphs
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Codex 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。