设图$G=(V(G),E(G))$, 其中$V(G)$称为顶点集或点集, 其元素称为顶点或点, $|V(G)|$表示顶点数. $E(G)$是边集, 可以为空集, $|E(G)|$表示边数.设边集$X\subseteq E(G)$, $G/X$是将$X$中每条边的两个端点粘在一起并删去在此过程中所产生的环得到的图.注意收缩后可能包含重边.为了方便, $G/\{e\}$简记为$G/e$, 其中$e\in E(G)$.如果$H$是$G$的子图, 则$G/E(H)$简记为$G/H$.设$V'$是$V(G)$的子集, $G-V'$表示删去$V'$中所有顶点以及与其相关联的边所得到的图.当$V'=\{v\}$时, $G-\{v\}$简记为$G-v$.设$V',V$均是$V(G)$的子集, 且$V'\subseteq V$, 用$V\setminus V'$表示从顶点集$V$中去掉$V'$.

$C_n$是一个长为$n$的圈. $n$ -轮$W_n$是由一个长为$n$的圈添加一个与圈上每个顶点都相邻的点得到的图.添加的顶点称为这个轮的中心.当$n$是偶数时, 称$W_n$为偶轮.否则, 称$W_n$为奇轮.

包含$G$的每个顶点的路称为$G$的哈密顿路. $P$是简单图$G$中的一条极大路指的是图$G$中不存在一条路$P'$使得$P\subset P'$.

图$G$中, 对任意一个顶点$v$, 用$N(v)$表示$v$的所有邻点构成的集合, 用$N_v$表示由$v$的所有邻点导出的子图.如果对任意一个顶点$v$, $N_v$都是$k$ -边连通的, 称图$G$是局部$k$ -边连通的. $K_1$中仅有一个顶点没有边, 则它是局部$k$ -边连通的, 这里$k\geq1$.任何一个连通的阶数至少是3的局部连通图是2 -边连通的.

$K_{1,3}$称为一个爪.从$K_5$中删掉一个4 -圈所得到的图称为沙漏, 用$H$表示.如果图$G$中不含有与$\{H,K_{1,3}\}$同构的导出子图, 称图$G$是无爪无沙漏图.

图论的发展与著名的四色问题紧密相连, Tutte在研究四色问题时引入了整数流概念.设$D(G)$表示图$G$的某个定向.对$V(G)$中的任意顶点$v$, 定义

$E_D^+(v)=\{e\in E(G)|v\mbox{是}e\mbox{的起点}\}, E_D^-(v)=\{e\in E(G)|v\mbox{是}e\mbox{的终点}\}.$

如果存在映射$f:E(G)\to \{\pm 1,\pm2,\cdots,\pm(k-1)\}$使得对任意顶点$v\in V(G)$有

$\sum\limits_{e\in E^+_D(v)}f(e)=\sum\limits_{e\in E^-_D(v)}f(e),$

那么称$G$存在处处非零$k$ -流.

1992年, Jaeger等人^[5]把整数流概念成功地推广到群连通性上.设$A$是一个非平凡的Abel加群, 其单位元为0.令$A^*=A-\{0\}$. $Z_m$是$m$阶循环群.定义$F(G,A)=\{f|f:E(G)\rightarrow A\}$, $F^*(G,A)=\{f|f:E(G)\rightarrow A^*\}$.对于任意的$f\in F^*(G,A)$, 令$f$的边界$\partial f$是从$V(G)$到$A$的一个函数使得对所有的$v\in V(G)$有

$\partial f(v)=\sum\limits_{e\in E_D^+(v)}f(e)-\sum\limits_{e\in E_D^-(v)}f(e),$

其中``$\sum$"表示在群$A$中的加法.

如果$\sum\limits_{v\in V(G)}b(v)=0$, 函数$b:V(G)\to A$称为$A$ -值零和函数.用$\mathbb{Z}(G,A)$表示图$G$上所有的零和函数.如果对于给定的$b\in \mathbb{Z}(G,A)$, 存在$G$的一个定向和$F^*(G,A)$中的一个函数$f$使得$\partial f=b$, 则称$f$为处处非零$(A,b)$ -流.处处非零$(A,0)$ -流称为处处非零$A$-流.特别地, 一个处处非零$k$ -流就是一个处处非零$Z_k$-流.如果对于任意的$b\in \mathbb{Z}(G,A)$, 都存在函数$f\in F^*(G,A)$使得$\partial f=b$, 那么我们称$G$是$A$ -连通的.用$\langle A\rangle$表示所有的$A$ -连通图的集合.在文献[12]中, Tutte证明了一个图存在处处非零$k$-流当且仅当它存在处处非零的$A$ -流, 其中$|A|=k$.因此如果$G$是$A$ -连通的, 则$G$存在处处非零$A$ -流.所以, $G$存在处处非零$k$ -流.反之却不成立, 即$G$存在处处非零$k$ -流时, $G$不一定是$A$ -连通的.虽然群连通是在有向图下定义的, 但实际上Jaeger等人^[5]证明了$G$的群连通性并不依赖于$G$的定向, 而且还提出了两个著名的猜想: $Z_3$ -和$Z_5$ -连通性猜想.这些猜想到目前为止仍旧是开放的.

群连通理论作为处处非零流理论的延伸, 不仅是解决一系列理论问题的重要方法与工具, 同时在通信网络设计、计算机科学等中都有非常重要的应用.目前对图的处处非零3 -流和$Z_3$ -连通性已经有了广泛的研究. Thomassen ^[11]证明了每个8 -边连通图是群$Z_3$ -连通的. Lai等人说明了阿贝尔Cayley图的群$Z_3$ -连通性. Lai等人^[9]证明了阶数为$n$的$k$ -边连通图中, 若$k\geq 4 log_2n$, 则$G$有处处非零3 -流. Alon等人^[1]进一步改进了该结论, 指出若$k\geq 2\log_2n$, 则$G$有处处非零3 -流. Fan等人^[3]还证明了每个三角连通的4 -边连通图是群$Z_3$ -连通的.有关连通图的研究可以参考文献[13].

近来, 度条件被用来保证图的群连通性的存在. Fan和Zhou^[4]提出了阶数为n的2-边连通的简单图, 如果每对相邻的顶点$x$和$y$满足$d(x)+d(y)\geq n+2$, 则$G$是群$Z_3$ -连通的当且仅当$G$不是$K_4$, 还证明了如果阶数为$n$的图$G$中任意两个相邻的顶点$x,y$满足$d(x)+d(y)\geq n$, 则除了几个特殊图以外图$G$有处处非零3 -流. Luo等人^[10]推广了Fan和Zhou的结论, 证明了满足Ore -条件的图除了12个图以外都是$Z_3$ -连通的. Li等人^[8]指出如果阶数为$n$的图$G$中任意两个不相邻的顶点$u,v$满足$\max\{d(u),d(v)\}\geq \frac{n}{2}$, 则除了一些特殊图以外$G$是群$Z_3$ -连通的或者能$A$ -收缩到$\{K_3,K_4,K_4^-,K_5^-\}$.

在$Z_3$ -连通性的研究中, Lai^[7]引入了局部连通的条件, 证明了每个2 -边连通的, 局部3 -边连通图是群$Z_3$ -连通的.本文中, 我们将降低局部边连通度, 并得到下述定理.

定理 1.1 设$G$是3 -边连通的无爪无沙漏图, 如果$G$是局部连通的, 则$G$不是群$Z_3$ -连通的当且仅当$G$是$K_4$或$W_5$.

以下两个引理是群连通的基本性质.

引理2.1 (见文献[6])设$A$是Abel群, 则下列结论成立:

(1) $K_1\in \langle A\rangle$.

(2) 若$e\in E(G)$且$G\in \langle A\rangle$, 则$G/e\in \langle A\rangle$.

(3) 若$H$是$G$的$A$-连通子图, 则$G/H\in \langle A\rangle$当且仅当$G\in \langle A\rangle$.

引理2.2 (见文献[2,5,6]设$A$是Abel群, 以下结论成立:

(1) 若$n\ge 5$, 则$K_n$和$K_n^-$是$A$ -连通的, 这里$|A|\geq 3$.

(2) $C_n$是$A$ -连通的当且仅当$|A|\geq n+1$.

(3) 若$k$是正整数, 则$W_{2k}\in \langle Z_3\rangle$, $W_{2k+1}\not\in \langle Z_3\rangle$.

设$u$是图$G$的一个顶点, $v,w$是$u$在图$G$中的两个邻点.如果$d(u)\geq 4$, 用$G_{[uv,uw]}$表示从$G$中删去边$uv,uw$再加上边$wv$构成的图, 即$G_{[uv,uw]}=G\cup \{wv \}- \{uv,uw\}$.

引理2.3 (见文献[6])设$A$是Abel群, $u,v,w$是$G$中的三个顶点, 并且$d_G(u)\ge 4$, $uv,wu\in E(G)$.若$G_{[uv, uw]}$是$A$ -连通的, 则$G$是$A$ -连通的.

如果图$G$中, 任意两个不相邻的顶点$x$和$y$, 都有$d(x)+d(y)\geq |V(G)|$, 称图$G$满足Ore -条件.

引理2.4 (见文献[10])一个阶数至少是3的简单图$G$, 若$G$满足Ore -条件, 则$G$不是群$Z_3$ -连通的当且仅当$G$是图 1中的12个图之一.

由引理2.4, 我们很容易得到下面的结论.

引理2.5 设$G$是3 -边连通的阶数$n\leq6$的简单图, 若$G$是无爪、无沙漏的局部连通图, 则$G$不是群$Z_3$ -连通的当且仅当$G$是$K_4$或$W_5$.

证 由于$G$是3 -边连通的简单图, 因此阶数$n\geq3$且$d(v)\geq3$.所以当$n\leq6$时, $G$满足Ore -条件.因为$d(v)\geq3$, 故$G$不是$G_3,G_4,G_5,G_6,G_7$.又由于$G$是无爪图, 所以$G$不是$G_9,G_{10}$.因为$G$是无沙漏图, 故$G$不是$G_{11},G_{12}$.最后, 根据$G$是局部连通图, 因此$G$不是$G_8$.由引理2.4, $G$不是群$Z_3$ -连通的当且仅当$G$是$G_1$或$G_2$, 即为$K_4$或$W_5$, 得证.

引理2.6 若图$G$是无爪的局部连通的简单图, 则对任意一个顶点$v\in V(G)$, $N_v$有一条哈密顿路.

证 反证, 设$P=x_1x_2\cdots x_k$是$N_v$中的一条极大路, 假设$N(v)\setminus V(P)\neq \emptyset$.由极大路的定义可知, $x_1,x_k$与$N(v)\setminus V(P)$中的顶点均不相邻, 否则与$P$是极大路相矛盾.在$N(v)\setminus V(P)$中任取两个顶点$u,w$, 有$uw\in E(G)$.否则, $\{v,x_1,u,w\}$的导出子图是$K_{1,3}$.因此$N(v)\setminus V(P)$的导出子图是完全图.若$k\leq2$, 则$e(\{x_1,\cdots,x_k\},N(v)\setminus V(P))=0$与$G$是局部连通图相矛盾, 所以$k\geq3$.当$x_1x_k\notin E(G)$时, 任取$x\in N(v)\setminus V(P)$, 则$\{v,x_1,x_k,x\}$的导出子图是$K_{1,3}$, 矛盾.因此$x_1x_k\in E(G)$.由于$G$是局部连通的, 故存在$x_i\in V(P)$及$y\in N(v)\setminus V(P)$使得$x_iy\in E(G)$.此时有一条长为$k+1$的路$P'=yx_{i+1}\cdots x_kx_1x_2\cdots x_{i-1}$, 这与$P$是极大路相矛盾, 因此$N(v)\setminus V(P)=\emptyset$.故$N_v$有一条哈密顿路.

引理2.7 设$G$是3 -边连通的阶数为$n$的简单图.如果$G$是无爪、无沙漏的局部连通图, 且至少有一个顶点的度不小于5, 则$G$中有一个群$Z_3$ -连通子图或$G$是轮$W_5$.

证 由引理的条件, 设$d(v)\geq5$.令$N(v)=\{v_1,v_2,\cdots v_t\}$, 这里$t\geq5$, 从而得$n\geq6$.下面分三种情形进行讨论.

情形 1 存在一个在$N_v$中度数为1的顶点.

不妨设$d_{N_v}(v_1)=1$.由引理2.6, 在$N_v$中存在一条哈密顿路, 不妨设这条路为$P=v_1v_2\cdots v_t$.由于$G$是无爪图, 则$v_3v_5\in E(G)$, 否则, $\{v,v_1,v_3,v_5\}$的导出子图是$K_{1,3}$, 矛盾.我们断言$v_2$与$\{v_4,v_5\}$中至少一个顶点相邻, 否则$\{v,v_1,v_2,v_4,v_5\}$的导出子图是沙漏$H$, 矛盾.若$v_2v_4\in E(G)$或者$v_2v_5\in E(G)$, 则$\{v,v_2,v_3,v_4,v_5\}$的导出子图中包含$k_5^-$.由引理2.2知, $k_5^-$是群$Z_3$ -连通的.

情形 2 $N(v)$中所有顶点在$N_v$中的度均等于2.

由于$N(v)$中所有顶点在$N_v$中的度均等于2, 所以$N_v$是一个圈, 不妨设$N_v=v_1v_2\cdots v_tv_1$.若$t\geq6$, 则$\{v,v_2,v_4,v_6\}$导出爪$K_{1,3}$, 矛盾.故$t=5$.若$n=6$, 则$G$是轮$W_5$.因此设$n\geq7$, 所以图$G$中还有异于$N[v]$中的顶点.由于$G$是3 -边连通图, 因此不妨设$v_1$还有一个邻点.又由于$G$是局部连通的, 所以存在$v_1$的一个邻点$u\in V(G)\setminus N[v]$, 使得$uv_2\in E(G)$或者$uv_5\in E(G)$.由对称性, 不妨设$uv_2\in E(G)$.

若$v_1$无其它邻点, 即$N(v_1)=\{v,v_2,v_5,u\}$.由于$d(u)\geq3$, 故除了$v_1,v_2$外, 还有其它的邻点.如果$uv_3\in E(G)$, 则$\{v,v_1,v_2,v_3,u\}$包含了一个$W_4$.由引理2.2知, $W_4$是群$Z_3$ -连通的.因此设$uv_3\notin E(G)$.如果$uv_4\in E(G)$, 由于$G$是无爪图, 所以$uv_5\in E(G)$.否则$\{v_4,v_3,v_5,u\}$导出一个爪, 得$d_{G^1}(u)\geq4$.令$N[v]\cup \{u\}$的导出子图为$G^1$.作图$G^1_{[uv_1,uv_2]}$, 则在$v_1,v_2$间有重边, 收缩这个2 -圈, 并重复收缩所有的2 -圈, 最后$G^1_{[uv_1,uv_2]}$收缩到$K_1$, 因此$G^1_{[uv_1,uv_2]}$是群$Z_3$ -连通的.由引理2.3知, $G^1$是群$Z_3$ -连通的.因此$u$与$v_3,v_4$均不相邻.

如果$uv_5\in E(G)$, 则$d_{G^1}(v_5)\geq4$.作图$G^1_{[v_5v_1,v_5u]}$, 则在$v_1,u$间有重边, 收缩这个2 -圈, 并重复收缩所有的2 -圈, 最后$G^1_{[v_5v_1,v_5u]}$收缩到$K_1$。因此$G^1_{[v_5v_1,v_5u]}$是群$Z_3$ -连通的.由引理2.3知, $G^1$是群$Z_3$ -连通的, 因此$u$与$v_5$也不相邻.又由于$G$是局部连通图, 故存在$u$的一个邻点$x$使得$xv_2\in E(G)$.此时$xv_3\in E(G)$, 否则$\{v_1,v_2,v_3,x\}$的导出子图是$K_{1,3}$.令$N[v]\cup \{u,x\}$的导出子图为$G^2$.作图$G^2_{[v_1u,v_1v_2]}$, 则在$v_2,u$间有重边, 收缩这个2-圈, 并重复收缩所有的2 -圈, 最后$G^2_{[v_1u,v_1v_2]}$收缩到$K_1$, 因此$G^2_{[v_1u,v_1v_2]}$是群$Z_3$ -连通的.由引理2.3知, $G^2$是群$Z_3$ -连通的.

若$v_1$有其它邻点$w$, 则$uw\in E(G)$, 否则有$K_{1,3}$.而且$uv_5\in E(G)$或$wv_5\in E(G)$, 否则$\{v_1,v,v_5,u,w\}$的导出子图是沙漏$H$.令$N[v]\cup \{u,w\}$的导出子图为$G^3$.作图$G^3_{[v_5v,v_5v_1]}$, 则$G^3_{[v_5v,v_5v_1]}$是群$Z_3$ -连通的.由引理2.3知, $G^3$是群$Z_3$ -连通的.

情形 3 $N(v)$中至少有一个顶点在$N_v$中的度不小于3, 其余顶点的度均不小于2.

不妨设$d_{N_v}(v_1)\geq3$.令$\{v_2,v_3,v_4\}\subseteq N(v_1)$, 则$\{v_2,v_3,v_4\}$之间必有一条边, 否则有$K_{1,3}$.不妨设$v_2v_3\in E(G)$.若$v_4$与$v_2$或$v_3$相邻, 则有$K^-_5$作为其子图.由引理2.2知, $K_5^-$是群$Z_3$ -连通的.所以$v_4$与$\{v_2,v_3\}$均不相邻.又由于$d_{N_v}(v_4)\geq2$, 故存在$v_j$与$v_4$相邻.若$v_j$与$\{v_2,v_3\}$均不相邻, 那么$\{v,v_2,v_3,v_4,v_j\}$的导出子图是$H$.故$v_j$ $(j\geq5)$与$v_2$或$v_3$相邻, 则$G$中有以$v$为中心点的轮$W_4$, 其4 -圈是: $v_1v_2v_jv_4v_1$或$v_1v_3v_jv_4v_1$.由引理2.2知, $W_4$是群$Z_3$ -连通的.故该引理得证.

设$G$是简单图, 将$G$中的一个群$Z_3$ -连通子图收缩成点$v^*$, 若在$v^*$处有2 -圈, 收缩这个2 -圈, 得到的收缩点仍用$v^*$表示, 重复这个过程, 直到图中无2 -圈, 最后得到的图记为$G^*$, 易知$G^*$是简单图.由于2 -圈是群$Z_3$ -连通的, 因此存在一个群$Z_3$ -连通子图$L$使得$G^*=G/L$.

引理2.8 设$G$是阶数为$n$的局部连通的简单图, $G^*$和$L$如上所述.设$L$是非平凡图, 如果$x\in V(L)$且$xv_1\in E(G)$, 则$v_1\in V(L)$.

证 因为$L$是连通的非平凡图, 则$L$中一定有$x$的一个邻点$u$.又$G$是局部连通图, 故在$u$和$v_1$之间存在一条路$P=uu_1u_2\cdots u_sv_1$且$\{u,u_1,u_2,\cdots,u_s\}\subseteq N(x)$.由于$u,x\in V(L)$, 且$G^*$是简单图, 所以$u_1\in V(L)$, 依此类推, $v_1\in V(L)$.

由引理2.8, 我们立刻得到下述结论.

推论2.9 设$G$是阶数为$n$的局部连通的简单图, 若$G$有一个非平凡的群$Z_3$ -连通子图, 则$G$是群$Z_3$ -连通的.

证 $G^*$和$L$如上所述.假设$G$不是$Z_3$ -连通的, 则$G^*$不是$K_1$.由于$G$是连通图, 故存在$x\in V(L)$及$v_1\notin V(L)$使得$xv_1\in E(G)$.由引理2.8知, $v_1\in V(L)$, 矛盾.故得证.

定理1.1的证明 根据引理2.5, 若$G$是$K_4$或$W_5$, 则$G$不是群$Z_3$ -连通的.故我们只需要证明必要条件成立.即证如果$G$不是群$Z_3$ -连通的, 则$G$是$K_4$或$W_5$.若$\triangle(G)\geq5$, 由引理2.7得, $G$有一个非平凡的群$Z_3$ -连通子图或$G$是$W_5$.由推论2.9知, 若$G$有一个非平凡的群$Z_3$ -连通子图, 则$G$是群$Z_3$ -连通的.由于$G$不是群$Z_3$ -连通的, 所以$G$是$W_5$.因此, 我们只需讨论$\triangle(G)\leq4$的情形.

若$\triangle(G)=3$.取$G$中的一个顶点$v$, 令$N(v)=\{v_1,v_2,v_3\}$.由引理2.6, 不妨设存在一条哈密顿路$P=v_1v_2v_3$.若$v_3$不是$v_1$的邻点, 由于$d(v_1)=3$且$G$是局部连通图, 则存在$u\in N(v_1)$使得$uv\in E(G)$或$uv_2\in E(G)$, 从而得$d(v)\geq4$或$d(v_2)\geq4$, 矛盾.故$v_3$是$v_1$的邻点, 所以$G$是$K_4$.

因此$\triangle(G)=4$.取$G$中的一个顶点$v$, 令$N(v)=\{v_1,v_2,v_3,v_4\}$.

如果所有的$v_i$ $(1\leq i\leq4)$在$N_v$中的度均为2, 由于$G$是局部连通图, 则$G$包含轮$W_4$.由引理2.2, $W_4$是群$Z_3$ -连通的.由推论2.9知, $G$是群$Z_3$ -连通的, 矛盾.

如果存在一个顶点$v_i$$(1\leq i\leq4)$在$N_v$中的度为3, 其余点的度至少为2.不妨设$d_{N_v}(v_1)=3$, 则$v_1v_2,v_1v_3,v_1v_4\in E(G)$.由于$G$中无爪, 所以$\{v_2,v_3,v_4\}$中至少有一条边.不妨设$v_2v_3\in E(G)$, 由于$d_{N_v}(v_4)\geq2$, 则$v_4$与$v_2$或$v_3$相邻, 此时$G$中有$K^-_5$.由引理2.2, $K^-_5$是群$Z_3$ -连通的.由推论2.9知, $G$是群$Z_3$ -连通的, 矛盾.

因此设存在一个顶点在$N_v$中的度为1, 不妨设这个点是$v_1$.由引理2.6, 在$N_v$中存在一条哈密顿路, 不妨设这条路为$P=v_1v_2v_3v_4$.

若$d(v_1)=3$, 令$u$是$v_1$的另外一个邻点.由于$G$是局部连通图, 所以$uv_2\in E(G)$.又因为$d(u)\geq3$且$G$是局部连通图, 故存在点$x\in N(u)$使得$xv_2\in E(G)$.若$x=v_3$, 则$G$包含轮$W_4$.由引理2.2, $W_4$是群$Z_3$ -连通的.由推论2.9知, $G$是群$Z_3$ -连通的, 矛盾.因此$x\neq v_3$, 此时$d(v_2)\geq5$, 矛盾.

若$d(v_1)=4$, 令$u,w$是$v_1$的另外两个邻点.由于$G$中没有爪, 故$uw\in E(G)$.因为$G$是局部连通图, 不妨设$v_2$与$u$相邻.又因为$d(w)\geq3$且$G$是局部连通图, 故存在点$x_1\in N(w)$使得$x_1u\in E(G)$.则$x_1\neq v_3$, 否则$d(v_3)\geq5$, 矛盾.若$x_1=v_4$, 由于$G$是局部连通图, 故$N_{v_4}$是连通的, 所以$v_3$与$u$或$w$相邻.若$v_3$与$u$相邻, 则$G$包含轮$W_4$.由引理2.2, $W_4$是群$Z_3$ -连通的.由推论2.9知, $G$是群$Z_3$ -连通的, 矛盾.故$v_3$与$w$相邻.令$N[v]\cup \{u,w\}$的导出子图为$G^1$, 作图$G^1_{[vv_1,vv_2]}$, 则在$v_1,v_2$间有重边, 收缩这个2 -圈, 并重复收缩所有的2 -圈, 最后$G^1_{[uv_1,uv_2]}$收缩到$K_1$.因此$G^1_{[uv_1,uv_2]}$是群$Z_3$ -连通的.由引理2.3知, $G^1$是群$Z_3$ -连通的, 故$x_1\neq v_4$.因为$d(x_1)\geq3$且$G$是局部连通图, 故存在点$x_2\in N(x_1)$使得$x_2w\in E(G)$.根据上面类似的讨论, 从而得$x_2\notin \{v_3,v_4\}$.依此类推, 我们得到一系列的点$x_3,x_4,\cdots$, 由于$G$是有限图, 不妨设这样的点终止于$x_k$.由以上讨论可知, $x_i\notin \{v_3, v_4\}$且$x_ix_{i-1},x_ix_{i-2}\in E(G)$, 这里$3\leq i\leq k$.

断言 如果$G$中除了上面所述的顶点外还包含有其它的顶点$y$, 则$yx_{k-1},yx_k\notin E(G)$.

断言的证明 反证, 若$y$与$x_{k-1}$相邻, 由于$N_{x_{k-1}}$是连通的且$\triangle(G)=4$, 从而得$yx_k\in E(G)$, 这与$x_k$的定义相矛盾, 故$y$与$x_{k-1}$不相邻.若$y$与$x_k$相邻, 由于$N_{x_k}$是连通的且$\triangle(G)=4$, 则存在$z\in N(x_k)$使得$zx_{k-1}\in E(G)$.这时$z$与$x_k$的定义相矛盾, 所以$y$与$x_k$也不相邻.

由断言知, $x_k$只能与$v_3$或$v_4$相邻.若$x_k$与$v_3$相邻, 由于$N_{v_3}$是连通的, 故$v_4x_k\in E(G)$.又由于$N_{x_k}$是连通的, 故$v_4x_{k-1}\in E(G)$.此时图$G$中无其它的顶点, 作图$G_{[vv_1,vv_2]}$, 则在$v_1,v_2$间有重边, 收缩这个2 -圈, 并重复收缩所有的2 -圈, 最后$G_{[vv_1,vv_2]}$收缩到$K_1$, 因此$G_{[vv_1,vv_2]}$是群$Z_3$ -连通的.由引理2.3知, $G$是群$Z_3$ -连通的, 故$x_k$与$v_3$不相邻.若$x_k$与$v_4$相邻, 由于$N_{v_4}$是连通的, 故存在$z\in N(v_4)$使得$zv_3,zx_k\in E(G)$.若$z\neq x_{k-1}$, 则与断言相矛盾.因此$z=x_{k-1}$, 此时$d(x_{k-1})\geq5$与$\triangle(G)=4$相矛盾.定理得证.