广义Petersen图P(4k,4)的交叉数

The Crossing Number of Generalized Petersen Graph P(4k,4)

摘要: 图的交叉数是图论中一个重要的部分，近百年来，国内外很多学者都对图的交叉数这一问题进行研究。由于证明难度较大，国内外关于图的交叉数领域的研究进展缓慢。本文主要对广义Petersen图P(4k,4)的交叉数进行研究。采用反证法和数学归纳法，将P(4k,4)的边集分成边不相交的4k组，讨论所有可能情况，从而证得P(4k,4)(k≥4)的交叉数的下界至少是2k。

Abstract: The crossing number of graphs is an important part of graph theory. In the past 100 years, many scholars at home and abroad have studied the problem of the crossing number of graphs. Due to the difficulty of proof, the research progress in the field of the crossing numbers at home and abroad is slow. This paper mainly studies the crossing number of generalized Petersen graph P(4k,4). The method of proof by contradiction and mathematical induction are adopted, the edge set of P(4k,4) is divided into 4k groups with disjoint edges, and discuss all possible situations to prove that the lower bound of the crossing number of P(4k,4)(k≥4) is at least 2k.

1. 交叉数研究进展

图的交叉数是图论中一个重要的部分，近百年来，国内外很多学者都对图的交叉数这一问题进行研究。图的交叉数问题的研究，起源于20世纪40年代砖厂遇到的难题。第二次世界大战时期，Turan [1] 发现运砖车沿铁轨向仓库运砖时，车很容易在铁轨交点的位置脱节。他因此想到通过减少铁轨交叉个数来降低损失的方法，交叉数的概念由此而来。Garey和Johnson [2] 证明了确定一个图的交叉数是NP-完全问题。由于证明难度较大，国内外关于图的交叉数领域的研究进展缓慢。研究者们根据图的结构对图加以分类，取得了一些研究成果，下面主要介绍了完全图，完全二部图以及广义Petersen图的部分研究成果。

1.1. 完全图

1960年，R. K. Guy [3] 对n个顶点的完全图 $K_n$ 的交叉数提出下面的猜想：

$cr\left(K_n\right)=\frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor \lfloor \frac{n-2}{2}\rfloor \lfloor \frac{n-3}{2}\rfloor$.

其中对任意实数x， $\lfloor x\rfloor$ 表示不超过x的最大整数。

1969年，R. K. Guy [4] 在文献中对完全图的交叉数进一步研究，验证了当 $n\le 10$ 时，猜想成立。

1970年，Kieitman [5] 在文献中给出了当n足够大时，完全图 $K_n$ 交叉数的下界：

$cr\left(K_n\right)\ge n\left(n-1\right)\left(n-2\right)\left(n-3\right)/80.$

2002年，Alcholzer，Aurenhammer和Krasserl [6] 用计算机穷举方法证明了 $K_{11}$ 和 $K_{12}$ 的交叉数分别是100和150，并给出了 $K_{13}$ 的交叉数等于229。

1.2. 完全二部图

1954年，Zarankiewicz [7] 给出了完全二部图 $K_{m,n}$ 交叉数的猜想：

$cr\left(K_{m,n}\right)=\lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor \lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor$.

1970年，Kieitman [5] 证明当 $\min \left(m,n\right)\le 6$ 时，Zarankiewicz的猜想成立。

1993年，Woodall [8] 验证了Zarankiewicz的猜想对于 $K_{7,7}$ 和 $K_{7,9}$ 成立。

2003年，N. H. Nahas [9] 进一步研究当m，n足够大时完全二部图的交叉数：

$cr\left(K_{m,n}\right)\ge \frac{1}{5}m\left(m-1\right)\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor +9.9\times {10}^{-6}{m}^2{n}^2$.

1.3. 广义Petersen图

关于Petersen图的交叉数学者们进行了广泛的研究。最早研究广义Petersen图在1981年，Exoo，Harary和Kabel [10] 证明了：

$\{\begin{array}{l}cr\left(P\left(n,2\right)\right)=0,如果n为偶数或者n=3;\\ cr\left(P\left(n,2\right)\right)=2,如果n=5;\\ cr\left(P\left(n,2\right)\right)=3,如果n为奇数或者n\ge 7.\end{array}$

1986年Fiorini [11] 对广义Petersen图的交叉数进行研究，计算出当 $n\ge 14$ 时所有 $P\left(n,k\right)$ 交叉数的具体值，然而Fiorini的证明存在错误。对于 $cr\left(P\left(9,3\right)\right)=2$ 给出了的数学证明，确定了 $cr\left(P\left(10,3\right)\right)=4$，并且

$\{\begin{array}{l}cr\left(P\left(3h,3\right)\right)=h,\left(h\ge 4\right);\\ h+1\le cr\left(P\left(3h+1,3\right)\right)\le h+3,\left(h\ge 3\right);\\ cr\left(P\left(3h+1,3\right)\right)=h+2,\left(h\ge 2\right)\text{.}\end{array}$

2002年，Richter和Salazar [12] 指出Fiorini的证明存在错误，用数学归纳法重新证明并更正了Fiorini的结论：

$\{\begin{array}{l}cr\left(P\left(3h,3\right)\right)=h,\left(h\ge 3\right);\\ cr\left(P\left(3h+1,3\right)\right)=3h+1,\left(h>2\right);\\ cr\left(P\left(3h+1,3\right)\right)=h+2,\left(h>2\right).\end{array}$

1997年Sarazin [13] 在其文章中证明了 $cr\left(P\left(10,4\right)\right)=4$。

Salazar [14] 给出了对于任意的 $k\ge 5$， $n\ge k$，有：

$\frac{2}{5}\left[\left(1-\frac{4}{k}\right)\left(n-k^4\right)\right]+\left(4k^2+1-k^3\right)\le cr\left(P\left(n,k\right)\right)\le \left(2-\frac{2}{k}\right)n+\left(\frac{k^2}{2}+\frac{k}{2}+1\right)$.

2004年，林晓惠 [15] 在其论文中得出了 $P\left(4k+2,2k\right)$ 等部分广义Petersen图的交叉数的上界。

2005年，马登举等人 [16] 证明了 $G\left(2m+1,m\right)$ 的交叉数。

2009年，杨元生等人 [17] 利用算法给出了 $n\ge 16$ 时 $P\left(n,k\right)$ 的交叉数的精确值。

Fiorinil和黄元秋等人 [18] 分别用不同方法证明了 $P\left(3k,k\right)$ 的交叉数。

2013年，郑百功 [19] 在硕士论文中证明了 $P\left(10,3\right)$ 的交叉数

2. 广义Petersen图P(4k,4)

设广义Petersen图 $P\left(\text{4}k,\text{4}\right)$ 中的顶点集 $V\left(P\left(4k,4\right)\right)=\left\{u_i,v_i|1\le i\le 4k\right\}$，边集 $E\left(P\left(4k,4\right)\right)=\left\{u_i{u}_{i+1},u_i{v}_i,v_i{v}_{i+4}|1\le i\le 4k\right\}$， $k\ge 3$，其中下标取模4k。设 $V\left(F_i\right)=\left\{u_i,u_{i+1},v_i,v_{i+4}\right\}$， $E\left(F_i\right)=\left\{u_i{u}_{i+1},u_i{v}_i,v_i{v}_{i+4}\right\}$ 和 $H_i=F_i\cup F_{i+4}$， $1\le i\le 4k$ 且 $k\ge 3$，其中下标取模4k。很容易得到 $\left\{F_1,F_2,\cdots ,F_t\right\}$ 是 $P\left(4k,4\right)$ 的一个可传递分解，并且 $\left\{H_1,H_2,\cdots ,H_t\right\}$ 是 $P\left(\text{4}k,\text{4}\right)$ 的可传递一致2覆盖，其中 $k\ge 3$，即

$E\left(P\left(4k,4\right)\right)={\displaystyle {\cup }_{i=1}^{4k}{F}_i}$

$2E\left(P\left(4k,4\right)\right)={\displaystyle {\cup }_{i=1}^{4k}{H}_i}$.

画法D下的交叉数用 $cr\left(D\right)$ 或 $c{r}_D\left(G\right)$ 表示。设H是G的子图且 $f_D\left(H\right)$ 是H到所有非负实数集合的映射：

$f_D\left(H\right)=c{r}_D\left(H\right)+c{r}_D\left(H,G\backslash E\left(H\right)\right)/2$.

设 $\left\{H_1,H_2,\cdots ,H_t\right\}$ 是G的一个可传递的一致k覆盖。假设 $H_{i,j}$ 是 $H_i,H_{i+1},\cdots ,H_j$ 的并集，下标取模t，G中每一条边最多出现在 $H_i,H_{i+1},\cdots ,H_j$ 中的一个，否则设 $H_{i,j}$ 表示多重图使 $V\left(H_{i,j}\right)=V\left(G\right)$， $E\left(G\right)\subseteq E\left(H_{i,j}\right)$，对于 $uv\in E\left(H_k\right)$，uv恰好出现在 $H_i,H_{i+1},\cdots ,H_j$ 的 $\mu \left(u,v\right)$ 个子图中， $\mu \left(u,v\right)$ 表示 $H_{i,j}$ 中连接u和v的平行边数目，其中 $i\le k\le j$。如果 $H_{i,j}$ 是多重图，那么

$f_D\left(H_{i,j}\right)={\displaystyle \underset{uv\in H_{i,j}}{\sum }\mu \left(u,v\right)f_D\left(uv\right)}$.

设c是一个正整数。对于 $1\le i\le t$，若存在一个正整数 $l_i$ 满足 $f_D\left(H_{i,i-1+l_i}\right)\ge l_{i}c$，则令 $L_i^D$ 为 $l_i$ 的最小值使 $f_D\left(H_{i,i-1+l_i}\right)\ge l_{i}c$，若不存在这样的正整数 $l_i$，则令 $L_i^D=+\infty$。

令 $C_i$ 为圈 $u_{i+1}{u}_i{v}_i{v}_{i+4}{u}_{i+4}{u}_{i+5}{v}_{i+5}{v}_{i+1}{u}_{i+1}$， $P_0=u_1{u}_2\cdots u_{4k}$ 和 $P_j=v_j{v}_{j+4}\cdots v_{4k-4+j}$， $1\le j\le 4$。对于路径P，如果 $u,v\in V\left(P\right)$，则 $uPv$ 表示P从u到v的连续顶点。

在本节中如果没有特别说明，假设i和k是正整数，当 $1\le i\le 4k,k\ge 5$ 时，设 $cr\left(P\left(4\left(k-1\right)k,4\right)\right)\ge 2\left(k-1\right)$ 且D为 $P\left(4k,4\right)$ 的一个好画法， $cr\left(D\right)<2k$。令 $V\left(B_i\right)=\left\{u_i,v_i\right\}$， $E\left(B_i\right)=\left\{u_i{v}_i\right\}$，由于 $P\left(4k,4\right)\backslash E\left(B_{i,i+3}\right)$ 是 $P\left(4\left(k-1\right),4\right)$ 的一个细分，我们得到以下结果。

引理2.1 $c{r}_D\left(B_{i,i+3}\right)+c{r}_D\left(B_{i,i+3},P\left(4k,4\right)\backslash E\left(B_{i,i+3}\right)\right)\le 1$。

根据Jordan曲线定理，我们有以下引理。

引理2.2在图G中，设C和 $C^{\prime }$ 为两个顶点不相交的圈， $P_k=u_1{u}_2\cdots u_k$ 为k阶路径且 $V\left(P_k\right)\cap V\left(C\right)=\varnothing$。假设D是G的一个好画法，那么 $c{r}_D\left(C,C^{\prime }\right)$ 是偶数；当 $u_1$ 和 $u_k$ 在 $D\left(C\right)$ 的同一区域时， $c{r}_D\left(C,P_K\right)$ 为偶数，否则为奇数。

为了后续证明叙述方便，现将引理2.2统称为引理2。

3. 广义Petersen图P(4k,4)的交叉数

引理3.1若 $L_i^D>2$ 且 $c{r}_D\left(H_{i,i+1}\right)=1$，则 $u_{i+2}$， $u_{i+6}$， $v_{i+8}$ 和 $v_{i+9}$ 都位于 $D\left(H_{i,i+1}\right)$ 划分的同一区域的同

一边界上。

证明：不失一般性，假设 $L_1^D>2$ 和 $c{r}_D\left(H_{1,2}\right)=1$。如果 $u_3$ 和 $u_7$ 不在 $D\left(H_{1,2}\right)$ 划分的同一区域的同一边界上，则由引理2可知，路径 $u_3{v}_3{v}_7{u}_7$ 和 $u_3{u}_4{v}_4{v}_8{u}_8{u}_7$ 交 $H_{1,2}$，因此 $L_i^D\le 2$，得出矛盾，则 $u_3$ 和 $u_7$ 在 $D\left(H_{1,2}\right)$ 划分的同一区域的同一边界上。如果 $v_9$ 和 $v_{10}$ 不在 $D\left(H_{1,2}\right)$ 划分的同一区域的同一边界上，则由引理2可知，路径 $v_9{u}_9{u}_{10}{v}_{10}$ 和 $v_9{v}_{13}{u}_{13}{u}_{14}{v}_{14}{v}_{10}$ 交 $H_{1,2}$，因此 $L_i^D\le 2$，得出矛盾，则 $v_9$ 和 $v_{10}$ 在 $D\left(H_{1,2}\right)$ 划分的同一区域的同一边界上。如果 $u_7$ 和 $v_9$ 不在 $D\left(H_{1,2}\right)$ 划分的同一区域的同一边界上，则由引理2可知，路径 $u_7{u}_8{u}_9{v}_9$ 和 $u_7{v}_7{v}_{11}{u}_{11}{u}_{10}{u}_9{v}_9$ 交 $H_{1,2}$，因此 $L_i^D\le 2$，得出矛盾，则 $u_7$ 和 $v_9$ 在 $D\left(H_{1,2}\right)$ 划分的同一区域。因此 $u_3$， $u_7$， $v_9$ 和 $v_{10}$ 都位于 $D\left(H_{1,2}\right)$ 划分的同一区域的同一边界上。

若 $L_i^D>2$ 且 $c{r}_D\left(H_{i,i+1}\right)\le 1$，由引3.1，我们得到如下结果。

引理3.2若 $L_i^D>2$ 且 $c{r}_D\left(C_i\right)=1$，则 $D\left(H_{i,i+1}\right)$ 与图1中的其中一个图同构。

引理3.3若 $L_i^D>2$ 且 $c{r}_D\left(C_i\right)=1$，则 $c{r}_D\left(C_i,u_{i+2}{v}_{i+2}{v}_{i+6}{u}_{i+6}\right)=0$。

证明：不失一般性，假设 $c{r}_D\left(C_1,u_3{v}_3{v}_7{u}_7\right)\ge 1$ 时 $L_1^D>2$ 且 $c{r}_D\left(C_1\right)=1$。通过 $L_1^D>2$，得到 $f_D\left(H_{1,2}\right)<2$。由于 $c{r}_D\left(C_1,u_3{v}_3{v}_7{u}_7\right)\ge 1$，由引理3.2和引理2得到 $c{r}_D\left(C_1,u_3{v}_3{v}_7{u}_7\right)\ge 2$，因此 $f_D\left(H_{1,2}\right)\ge 2$，得出矛盾。

Figure 1. Subdrawings of D

图1. D的子画法

引理3.4若 $L_i^D>2$ 且 $D\left(H_{i,i+1}\right)$ 同构于图1(a)，则 $L_i^D\le 3$。

证明：反证法，不失一般性，假设 $L_1^D\ge 4$ 且 $D\left(H_{1,2}\right)$ 同构于图1(a)。通过 $L_1^D\ge 4$，得到 $f_D\left(H_1\right)<1$ 和 $f_D\left(H_{1,3}\right)<3$。由于 $B_5$ 被交，由引理2.1可知在画法D下 $B_3$ 和 $B_7$ 是干净的。则在好的画法D下有 $c{r}_D\left(u_3{v}_3{v}_7{u}_7\right)=0$。由引理7得到 $c{r}_D\left(C_1,u_3{v}_3{v}_7{u}_7\right)=0$。

由 $f_D\left(H_{1,3}\right)<3$ 得到 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)\le 1$。因此我们只需考虑以下情况:

情况1 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)=1$。

情况2 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)=0$。

引理3.5若 $L_i^D>2$ 且 $D\left(H_{i,i+1}\right)$ 同构于图1(b)，则 $L_i^D\le 4$。

证明：反证法，不失一般性，假设 $L_1^D\ge 5$ 且 $D\left(H_{1,2}\right)$ 同构于图1(b)。通过 $L_1^D\ge 5$，得到 $f_D\left(H_{1,2}\right)<2$， $f_D\left(H_{1,3}\right)<3$ 和 $f_D\left(H_{1,4}\right)<4$。由于 $B_6$ 被交，由引理2.1可知在画法D下 $B_{3,4}$ 和 $B_{7,8}$ 都是干净的。因此 $c{r}_D\left(u_3{v}_3{v}_7{u}_7\right)=0$。由引理3.3得到 $c{r}_D\left(C_1,u_3{v}_3{v}_7{u}_7\right)=0$。由 $f_D\left(H_{1,2}\right)<3$ 得到 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)\le 1$。因此我们考虑以下情况。

情况1 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)=0$。

情况2 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)=1$。

引理3.6若 $L_i^D>2$ 且 $D\left(H_{i,i+1}\right)$ 同构于图1(c)，则 $L_i^D\le 4$。

证明：反证法，不失一般性，假设 $L_1^D\ge 5$ 且 $D\left(H_{1,2}\right)$ 同构于图1(c)。通过 $L_1^D\ge 5$，得到 $f_D\left(H_1\right)<1$, $f_D\left(H_{1,3}\right)<3$ 和 $f_D\left(H_{1,4}\right)<4$。由于 $B_5$ 被交，由引理4可知在画法D下 $B_{2,4}$ 和 $B_{6,8}$ 都是干净的。因此 $c{r}_D\left(u_3{v}_3{v}_7{u}_7\right)=0$。由引理7得到 $c{r}_D\left(C_1,u_3{v}_3{v}_7{u}_7\right)=0$。由 $f_D\left(H_{1,3}\right)<3$ 得到 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)\le 1$。因此我们考虑以下情况。

情况1 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)=0$。

情况2 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)=1$。

引理3.7若 $L_i^D\ge 5$ 且 $D\left(H_{i,i+1}\right)$ 同构于图1(d)，则 $D\left(H_{i,i+1}\cup u_{i+2}{v}_{i+2}{v}_{i+6}{u}_{i+6}\right)$ 与图2同构，且 $u_{i+3}$ 位于 $R_0$ 或 $R_1$ 区域，如图2所示。

Figure 2. Subdrawings of D

图2. D的子画法

证明：不失一般性，假设 $L_1^D\ge 5$ 且 $D\left(H_{1,2}\right)$ 同构于图1(d)。通过 $L_1^D\ge 5$，得到 $f_D\left(H_1\right)<1$， $f_D\left(H_{1,2}\right)<2$， $f_D\left(H_{1,3}\right)<3$ 和 $f_D\left(H_{1,4}\right)<4$。由于 $B_2$ 和 $B_5$ 被交，由引理2.1可知在画法D下 $B_{3,4}$ 和 $B_{6,8}$ 都是干净的。因此 $c{r}_D\left(u_3{v}_3{v}_7{u}_7\right)=0$。

由 $f_D\left(H_{1,3}\right)<3$ 得到 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)\le 1$。由 $f_D\left(H_1\right)<1$，可知在画法D下 $v_5{v}_9$ 是干净的。由引理3.3得到 $c{r}_D\left(C_1,u_3{v}_3{v}_7{u}_7\right)=0$。当 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)=1$ 时， $D\left(H_{1，2}\cup u_3{v}_3{v}_7{u}_7\right)$ 与图3(a)，图3(b)和图3(c)中的一个图同构。

Figure 3. Subdrawings of D

图3. D的子画法

引理3.8若 $L_i^D\ge 5$， $D\left(H_{i,i+1}\cup u_{i+2}{v}_{i+2}{v}_{i+6}{u}_{i+6}\right)$ 与图2同构且 $u_{i+3}$ 位于 $R_1$ 区域，则 $L_i^D=5$。

引理3.9若 $L_i^D\ge 5$， $D\left(H_{i,i+1}\cup u_{i+2}{v}_{i+2}{v}_{i+6}{u}_{i+6}\right)$ 与图2同构且 $u_{i+3}$ 位于 $R_0$ 区域，则 $L_i^D=5$。

证明：反证法，不失一般性，假设 $L_1^D\ge 6$ 时 $D\left(H_{1,2}\cup u_3{v}_3{v}_7{u}_7\right)$ 同构于图2且 $u_4$ 在 $R_0$ 中。通过 $L_1^D\ge 6$，得到 $f_D\left(H_1\right)<1$， $f_D\left(H_{1,2}\right)<2$， $f_D\left(H_{1,3}\right)<3$， $f_D\left(H_{1,4}\right)<4$ 和 ${\displaystyle {\sum }_{i=1}^5{f}_D}\left(H_i\right)<5$。由于 $B_2$ 和 $B_5$ 被交，由引理2.1可知在画法D下 $B_{3,4}$ 和 $B_{6,8}$ 都是干净的。由引理2以及 $f_D\left(H_{1,4}\right)<4$ 可知 $c{r}_D\left(u_4{u}_5,C_2\right)=1$。若 $c{r}_D\left(u_4{u}_5,H_{1,2}\right)=1$，由 $f_D\left(H_{1,4}\right)<4$ 可知 $c{r}_D\left(u_4{u}_5,v_3{v}_7\right)\le 1$。

假设 $c{r}_D\left(u_4{u}_5,H_{1,2}\right)=1$ 且 $c{r}_D\left(u_3{u}_4,v_3{v}_7\right)=0$。此时 $D\left(H_{1,2}\cup F_3\cup B_7\cup u_4{u}_5\right)$ 与图4(a)，图4(b)和图4(c)其中一个图同构。

Figure 4. Subdrawings of D

图4. D的子画法

假设 $c{r}_D\left(u_4{u}_5,H_{1,2}\right)=1$ 且 $c{r}_D\left(u_3{u}_4,v_3{v}_7\right)=1$。此时 $D\left(H_{1,2}\cup F_3\cup B_7\cup u_4{u}_5\right)$ 与图5(a)，图5(b)和图5(c)其中一个图同构。

Figure 5. Subdrawings of D

图5. D的子画法

假设 $c{r}_D\left(u_4{u}_5,v_3{v}_7\right)=1$。由 $f_D\left(H_{1,4}\right)<4$，得到 $c{r}_D\left(u_3{u}_4,H_{1,2}\cup v_3{v}_7\right)+c{r}_D\left(u_4{u}_5,H_{1,2}\right)\le 1$。此时 $D\left(H_{1,2}\cup F_3\cup B_7\cup u_4{u}_5\right)$ 与图6(a)，图6(b)和图6(c)其中一个图同构。

Figure 6. Subdrawings of D

图6. D的子画法

引理3.10若 $L_i^D>2$ 且 $D\left(H_{i,i+1}\right)$ 同构于图1(e)，则 $L_i^D\le 5$。

证明：不失一般性，假设 $L_1^D\ge 6$ 且 $D\left(H_{1,2}\right)$ 同构于图1(e)。通过 $L_1^D\ge 6$，得到 $f_D\left(H_1\right)<1$， $f_D\left(H_{1,3}\right)<3$ $f_D\left(H_{1,4}\right)<4$ 和 ${\displaystyle {\sum }_{i=1}^5{f}_D}\left(H_i\right)<5$。由于 $B_2$ 和 $B_5$ 被交，由引理2.1可知在画法D下 ${\mathrm{B}}_{3,4}$ 和 ${\mathrm{B}}_{6,8}$ 都是干净的。因此 ${\mathrm{cr}}_D\left({\mathrm{u}}_3{\mathrm{v}}_3{v}_7{\mathrm{u}}_7\right)=0$。

引理3.11若 $L_i^D>2$ 且 $D\left(H_{i,i+1}\right)$ 同构于图1(f)，则 $L_i^D\le 5$。

证明：反证法，不失一般性，假设 $L_1^D\ge 6$ 且 $D\left(H_{1,2}\right)$ 同构于图1(f)。通过 $L_1^D\ge 6$，得到 $f_D\left(H_1\right)<1$， $f_D\left(H_{1,3}\right)<3$， $f_D\left(H_{1,4}\right)<4$ 和 ${\displaystyle {\sum }_{i=1}^5{f}_D}\left(H_i\right)<5$。由于 $f_D\left(H_1\right)<1$，可知在画法D下 $v_3{v}_7$ 是干净的。由引理7得到 $c{r}_D\left(C_1,u_3{v}_3{v}_7{u}_7\right)=0$。由 $f_D\left(H_{1,3}\right)<3$ 得到 $c{r}_D\left(u_3{v}_3{v}_7{u}_7\right)\le 1$。

当 $c{r}_D\left(u_3{v}_3{v}_7{u}_7\right)=1$ 时。由引理2可知有路径 $v_{10}{P}_2{v}_2$ 交 $H_{1,2}\cup u_3{v}_3{v}_7{u}_7$。由 $f_D\left(H_{1,3}\right)<3$，得到 $c{r}_D\left(u_3{u}_4{u}_5,H_{1,2}\cup u_3{v}_3{v}_7{u}_7\right)=0$，且有路径 $v_9{u}_9{u}_{10}{v}_{10}$， $v_9{v}_{13}{u}_{13}{u}_{12}{u}_{11}{v}_{11}{v}_7$ 和 $u_7{P}_0{u}_1$ 交 $H_{1,2}\cup F_3\cup B_7\cup u_4{u}_5$，与 $f_D\left(H_{1,4}\right)<4$ 相矛盾。因此 $c{r}_D\left(u_3{v}_3{v}_7{u}_7\right)=0$。由 $f_D\left(H_{1,3}\right)<3$ 得到 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)\le 1$。因此我们考虑以下情况。

情况1 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)=1$。

情况2 $c{r}_D\left(H_{1,2},u_3{v}_3{v}_7{u}_7\right)=0$。

综上对于且时，总有。

4. 结论

本文通过反证法和数学归纳法证明广义Petersen图的交叉数，给出相应的好的画法，通过结合不同的计数公式和特殊的定义，对的边进行分类，探究每组边上的交叉计数，最终验证关于图在且时交叉数的下界至少等于2k，即。