Petersen染色猜想的可能最小反例

The Possible Minimum Counterexample of Petersen Colouring Conjecture

摘要: Petersen染色猜想是图论在完美匹配方向上的一个仍未被证明的重要猜想，其表述为任意一个无桥三正则图都有Petersen染色。1985年，Jaeger证明了Petersen染色猜想等价于任意一个无桥三正则图都有normal 5-边染色。若无桥三正则图G有一个正常5-边染色，对于图G中的任一条边，其四条邻边与这条边总共用了3种或5种颜色，则称该正常5-边染色是图G的一种normal 5-边染色，其中与邻边共用了3种颜色的边被称为穷边，与邻边共用了5种颜色的边被称为富边。关于这两个猜想的结论大多是在一些特殊图类上，但对于一些长久存在的猜想，也有部分学者考虑其可能最小反例的性质，本文从Petersen染色猜想的等价猜想的性质出发研究Petersen染色猜想的可能最小反例的性质，证得Petersen染色猜想的可能最小反例必然是循环4-边连通的。

Abstract: Petersen colouring conjecture is an important unresolved conjecture in graph theory in the direction of perfect matchings, which states that every bridgeless cubic graph has a Petersen colouring. In 1985, Jaeger proved that the Petersen colouring conjecture is equivalent to the statement that every bridgeless cubic graph has a normal 5-edge-colouring. If a bridgeless cubic graph G has a normal 5-edge-colouring such that for any edge in graph G, the four adjacent edges together with this edge use either 3 or 5 colours, this normal 5-edge-colouring is called a normal 5-edge-colouring of graph G, where edges sharing 3 colours with adjacent edges are called poor edges and edges sharing 5 colours with adjacent edges are called rich edges. Most conclusions about these two conjectures are on some special classes of graphs, but for some long-standing conjectures, some scholars have also considered the properties of their possible minimum counterexample. This paper studies the properties of possible minimum counterexample of the Petersen colouring conjecture from the perspective of the equivalent conjecture’s properties and proves that a possible minimum counterexample of the Petersen colouring conjecture must be cyclically 4-edge-connected.

1. 引理

记petersen图为$P_{10}$ ，若无桥三正则图G存在映射$\phi :E\left(G\right)\to E\left(P_{10}\right)$ ，使得对于图G中任意一点v，$P_{10}$ 中都存在一点w满足$\phi \left({\partial }_G\left\{v\right\}\right)={\partial }_{P_{10}}\left\{w\right\}$ ，则称图G有Petersen染色。

图G的正常k-边染色是一个从边到颜色集$\left\{1,2,\cdots ,k\right\}$ 的映射$\phi :E\left(G\right)\to \left\{1,2,\cdots ,k\right\}$ ，使得图G中任意两条相邻的边在映射$\phi$ 下是不同的颜色。若图G有正常k-边染色，但无正常(k−1)-边染色，则称图G是k-边可染的。不是3-边可染的无桥三正则图被称为snark。若无桥三正则图G有一个正常5-边染色，对于图G中的任一条边，其四条邻边与这条边总共用了3种或5种颜色，则称该正常5-边染色是图G的一种normal 5-边染色，其中与邻边共用了3种颜色的边被称为穷边，与邻边共用了5种颜色的边被称为富边。

Jaeger于1985年[1]初步表述了Petersen染色猜想，提出了如下猜想2，并证明了这两个猜想是等价的，后于1988年[2]正式提出Petersen染色猜想。

猜想1 (Petersen染色猜想[2])任意一个无桥三正则图都有Petersen染色。

猜想2 [1] 任意一个无桥三正则图都有normal 5-边染色。

目前关于这两个猜想的可能最小反例性质的结果比较少，大部分学者探究的是使得猜想成立的图类，例如下述定理1和定理2，虽然定理1与定理2未直接参与本文主要定理的推导过程，但这两项成果聚焦于图结构的正向生成，与本文可能最小反例性质分析共同构成了对这两个猜想的多维度探究。

2024年，Sedlar和Škrekovski [3]证明了如下结论：

定理1 [3] 若一个snark G有normal 5-边染色，C为G中的一个偶圈，对于圈C上的点用图$A$ 或$A^{\prime }$ 替换，边用由Petersen图得到的图B替代得到的图仍为snark且有normal 5-边染色，见图1。

2026年，Zhou，Hao和Luo等人[4]证明了如下结论：

定理2 [4] 若一个无桥三正则图G有normal 5-边染色，C为G中的一个圈，对于圈C上的点用图Z替换得到的图仍有normal 5-边染色，见图2。

对于一些长久存在的猜想，也有部分学者研究其可能最小反例的性质。Fulkerson于1971年提出的Berge-Fulkerson猜想[5]以及Fan和Raspaud于1994年提出的Fan-Raspaud猜想[6]是图论在完美匹配方向上的两个重要猜想，Berge-Fulkerson猜想是Petersen染色猜想的推论，可推出Fan-Raspaud猜想。

Figure 1. Replacement diagram A' (left)、A' (middle) of vertices and replacement diagram B (right) of edges in Theorem 1

图1. 定理1中点的替换图A (左图)、A' (中间的图)和边的替换图B (右图)

Figure 2. Replacement diagram Z of vertices in Theorem 2

图2. 定理2中点的替换图Z

猜想3 (Berge-Fulkerson猜想[5])对于任意一个无桥三正则图，都存在6个完美匹配，使得每条边恰好被2个完美匹配覆盖。

猜想4 (Fan-Raspaud猜想[6])任意一个无桥三正则图都有3个完美匹配$M_1,M_2,M_3$ ，使得$M_1\cap M_2\cap M_3=\varnothing$ 。

2019年，Mkrtchyan和Vardanyan [7]提出了下述猜想5，并证明了该猜想的可能最小反例的如下循环边连通度：

猜想5 [7] 图G是一个无桥三正则图，边e，f，g是图G中与同一个点相关联的三条边，i，j，k是三个实数，满足如下条件：

$i+j+k=3,0\le i,j,k\le 2,$

则G包含一个FR-triple C，使得

$v_C\left(e\right)=i,v_C\left(f\right)=j,v_C\left(g\right)=k.$

定理3 [7] 猜想5的可能最小反例必然是循环4-边连通的snark。

2020年，Mazzuoccolo和Zerafa [8]证明了上述猜想5等价于Fan-Raspaud猜想。

2020年，Máčajová和Mazzuoccolo [9]证明了Berge-Fulkerson猜想的可能最小反例的如下循环边连通度：

定理4 [9] 若Berge-Fulkerson猜想存在反例，则其最小反例必然是循环5-边连通的snark。

本文从猜想2的性质出发，探究Petersen染色猜想的可能最小反例的循环边连通度，得到如下结果：

定理5 Petersen染色猜想的可能最小反例必然是循环4-边连通的。

2. 定理5的证明

本章证明了定理5，即证明了Petersen染色猜想(猜想1)的可能最小反例是循环4-边连通的。

定理5的证明 因Petersen染色猜想等价于猜想2，故可据猜想2的性质探究Petersen染色猜想的可能最小反例的循环边连通度。假设图G为猜想2的最小反例，因图G无桥，故图G无循环1-边割。

若图G有循环2-边割$S_2=\left\{e_1,e_2\right\}$ ，$S_2$ 将图G分成两个有圈的分支，它们的点集分别为$V_1$ 和$V_2$ ，这两个分支的阶都不小于3，记$e_1=u_1{v}_1$ ，$e_2=u_2{v}_2$ ，其中$u_1,u_2\in V_1$ ，$v_1,v_2\in V_2$ 。在图G中删去边$e_1,e_2$ ，连接$u_1$ 和$u_2$ 、$v_1$ 和$v_2$ ，两条边分别记为$f_1$ 和$f_2$ ，则就得到两个比图G小的有圈三正则图$G_1$ 和$G_2$ ，如图3。

Figure 3. The minimum counterexample G (left) of Conjecture 2 and two smaller cubic graphs with cycle than G (right)

图3. 猜想2的最小反例G (左图)和两个比G小的有圈三正则图(右图)

图$G_i$ 无桥，否则，若图$G_i$ 有桥，不妨以图$G_1$ 为例，若桥不是边$f_1$ ，则该桥也是图G的桥，这与图G无桥矛盾；若桥是边$f_1$ ，将图$G_1$ 分为两个分支，它们的点集分别为$V_1{}^{\prime }$ 和$V_1{}^{\prime \text{}\prime }$ ，点$u_1$ 和点$u_2$ 不在同一个分支内，不妨设点$u_1$ 在点集$V_1{}^{\prime }$ 中，点$u_2$ 在点集$V_1{}^{\prime \text{}\prime }$ 中，此时图$G_1$ 及图G如下图4，显然边$e_1$ 为图G的桥，这与图G无桥矛盾，故图$G_i$ 无桥，故图$G_i$ 为比图G小的无桥三正则图。

Figure 4. The graph G₁ (left) and G (right) when the bridge of the graph G₁ is edge f₁

图4. 图G1的桥为边f₁时的图G1 (左图)和图G (右图)

因图G为猜想2的最小反例，故图$G_1$ 和$G_2$ 都有normal 5-边染色，通过颜色的置换，使得边$f_1$ 和$f_2$ 都染颜色1，与点$u_1$ 相邻的除边$f_1$ 外的两条边分别染颜色2和颜色3，与点$v_1$ 相邻的除边$f_2$ 外的两条边分别染颜色2和颜色3，则图$G_1$ 和$G_2$ 都会有如下两种情况，见图5。

(1) 与点$u_2$ ($v_2$ )相邻的除边$f_1$ ($f_2$ )外的两条边分别染颜色2和颜色3；

(2) 与点$u_2$ ($v_2$ )相邻的除边$f_1$ ($f_2$ )外的两条边分别染颜色4和颜色5。

在图G中，对边$e_1$ 和$e_2$ 都染颜色1，其他边染图$G_1$ 和$G_2$ 中对应的边的颜色，可得到图G的一个正常5-边染色。在图G的这种正常5-边染色下，除边$e_1$ 和$e_2$ 外的其他边显然都是穷边或富边；边$e_1$ 及其四条邻边共用了3种颜色进行染色，故边$e_1$ 为穷边；若图$G_1$ 和$G_2$ 都是情况1或都是情况2，则边$e_2$ 及其四条邻边共用了3种颜色进行染色，故边$e_2$ 是穷边，若图$G_1$ 和$G_2$ 一个是情况1，另一个是情况2，则边$e_2$ 及其四条邻边共用了5种颜色进行染色，故边$e_2$ 是富边，因此，图G中任意一条边在该正常5-边染色下都是穷边或富边，故该正常5-边染色即为图G的normal 5-边染色，这与图G为猜想2的反例矛盾，故图G无循环2-边割。

Figure 5. Case 1 (left) and case 2 (right)

图5. 情况1 (左图)和情况2 (右图)

若图G有循环3-边割$S_3=\left\{e_1,e_2,e_3\right\}$ ，$S_3$ 将图G分成两个有圈的分支，它们的点集分别为$V_1$ 和$V_2$ ，这两个分支的阶都不小于3，记$e_1=u_1{v}_1$ ，$e_2=u_2{v}_2$ ，$e_3=u_3{v}_3$ ，其中$u_1,u_2,u_3\in V_1$ ，$v_1,v_2,v_3\in V_2$ 。在图G中删去边$e_1,e_2,e_3$ ，加上两个点u和v，点u分别与点$u_1,u_2,u_3$ 连接，三条边分别记为$f_1,f_2,f_3$ ，点v分别与点$v_1,v_2,v_3$ 连接，三条边分别记为$g_1,g_2,g_3$ ，则就得到两个比图G小的有圈三正则图$G_1$ 和$G_2$ ，如图6。

Figure 6. The minimum counterexample G (left) of Conjecture 2 and two smaller cubic graphs with cycle than G (right)

图6. 猜想2的最小反例G (左图)和两个比G小的有圈三正则图(右图)

图$G_i$ 无桥，否则，若图$G_i$ 有桥，不妨以图$G_1$ 为例，若桥不是边$f_i$ ，则该桥也是图G的桥，这与图G无桥矛盾；若桥是边$f_i$ ，不妨设是边$f_1$ ，将图$G_1$ 分为两个分支，它们的点集分别为$V_1{}^{\prime }$ 和$V_1{}^{\prime \text{}\prime }$ ，点$u_1$ 和点u不在同一个分支内，不妨设点$u_1$ 在点集$V_1{}^{\prime }$ 中，点u在点集$V_1{}^{\prime \text{}\prime }$ 中，则点$u_2$ 和点$u_3$ 也在点集$V_1{}^{\prime \text{}\prime }$ 中，此时图$G_1$ 及图G如下图7，显然边$e_1$ 为图G的桥，这与图G无桥矛盾，故图$G_i$ 无桥，故图$G_i$ 为比图G小的无桥三正则图。

因图G为猜想2的最小反例，故图$G_1$ 和$G_2$ 都有normal 5-边染色，通过颜色的置换，使得边$f_1$ 和$g_1$ 都染颜色1，边$f_2$ 和$g_2$ 都染颜色2，边$f_3$ 和$g_3$ 都染颜色3，则图$G_1$ 中的边$f_i$ 的除$f_j$ 和$f_k$ 外的两条邻边($i,j,k\in \left\{1,2,3\right\}$ ，且互不相等)，以及图$G_2$ 中的边$g_i$ 除$g_j$ 和$g_k$ 外的两条邻边都会有如下两种情况，见图8。

Figure 7. The graph G₁ (left) and G (right) when the bridge of the graph G₁ is edge f₁

图7. 图G1的桥为边f₁时的图G1 (左图)和图G (右图)

(1) 边$f_i$ ($g_i$ )的除$f_j$ ($g_j$ )和$f_k$ ($g_k$ )外的两条邻边分别染颜色j和颜色k；

(2) 边$f_i$ ($g_i$ )的除$f_j$ ($g_j$ )和$f_k$ ($g_k$ )外的两条邻边分别染颜色4和颜色5。

Figure 8. Case 1 (left) and case 2 (right)

图8. 情况1 (左图)和情况2 (右图)

在图G中，对边$e_1$ 染颜色1，边$e_2$ 染颜色2，边$e_3$ 染颜色3，其他边染图$G_1$ 和$G_2$ 中对应的边的颜色，可得到图G的一个正常5-边染色。在图G的这种正常5-边染色下，除边$e_1$ 、$e_2$ 和$e_3$ 外的其他边显然都是穷边或富边；对于这三条边中的任意一条边$e_i$ ，若图$G_1$ 和$G_2$ 都是情况1或都是情况2，则它和它的四条邻边共用了3种颜色进行染色，故边$e_i$ 是穷边，若图$G_1$ 和$G_2$ 一个是情况1，另一个是情况2，则它和它的四条邻边用了5种颜色进行染色，故边$e_i$ 是富边，因此，图G中任意一条边在该正常5-边染色下都是穷边或富边，故该正常5-边染色即为图G的normal 5-边染色，这与图G为猜想2的反例矛盾，故图G无循环3-边割。综上，因图G无循环1-边割、循环2-边割和循环3-边割，故图G必然是循环4-边连通的，即猜想2的可能最小反例必然是循环4-边连通的，因猜想2等价于Petersen染色猜想，故Petersen染色猜想的可能最小反例必然是循环4-边连通的，定理5得证。

3. 总结与展望

本文从Petersen染色猜想的等价猜想的性质出发研究Petersen染色猜想的可能最小反例的性质，证得Petersen染色猜想的可能最小反例必然是循环4-边连通的。其循环边连通度能否得到进一步提高是一个可以继续研究的问题，但在考虑可能最小反例存在循环4-边割时，会存在无法由两个更小的图的normal 5-边染色延拓得到可能最小反例的normal 5-边染色的情况，需要对这两个更小的图的normal 5-边染色进行改变，这是一个比较困难的问题。