极小3-连通平面图的构造

The Structure of Minimally 3-Connected Planer Graphs

摘要: 设$\mathcal{G}$ 是由满足以下条件的3-连通平面二部图所组成的图类：$\mathcal{G}$ 的一部是3度点的集合，另外一部是度至少为4的点的集合。本文证明了若G是极小3-连通平面图且G中不存在边e使得G/e或G/e\f是极小3-连通平面图，则$G\in \mathcal{G}$ ，这里f与e相邻于一个3度点。

Abstract: Let $\mathcal{G}$ be a set of minimally 3-connected planer graphs such that every member of $\mathcal{G}$ is a bipartite graph with one parts of vertices of degree three and the other parts of degree at least four. Let G be a minimally 3-connected planar graph. This paper show that if G has no edge e such that either G/e or G/e\f is minimally 3-connected planar graph then $G\in \mathcal{G}$ ; here e and f are two edges incident to a vertex of degree 3.

1. 引言

本文所考虑的图都是简单图。设$G=\left(V\left(G\right),E\left(G\right)\right)$ ，其中$V\left(G\right)$ 是G的顶点集合，$V\left(G\right)$ 是G的边集合。对于子集$T\subseteq V\left(G\right)$ ，若$G-T$ 是不连通的，则称T是G的一个点割。若$\left|T\right|=k$ ，则称T是一个k-点割。若$\left|V\left(G\right)\right|\ge k$ 且G中没有$k-1$ -点割，则我们称G是k-连通的。对任意$x\in V\left(G\right)$ ，$d\left(x\right)$ 表示x的度。设$A\subseteq V\left(G\right)$ ，用$G\left[A\right]$ 表示G的由顶点集A导出的子图，用$G-A$ 表示图G去掉顶点集A所得到的图。

设T是一个点割且$\left|T\right|=\kappa \left(G\right)$ ，若A是$G-T$ 至少一个分支但不是所有分支的并，则称A是一个T-断片。在不引起混淆的情况，我们简称A是一个断片。若A是一个T-断片，则易见$\overline{A}:=G-T-A$ 也是T-断片。若断片A中任意真子集都不再是断片，则称A为端片。设G是k-连通图，${\mathcal{T}}_0$ 是G中所有k-点割的集合。取$\mathcal{T}\subseteq {\mathcal{T}}_0$ ，若$N\left(A\right)\in \mathcal{T}$ 则称一个断片A是一个$\mathcal{T}$ -断片。设A是$\mathcal{T}$ -断片且A的任意真子集都不再是$\mathcal{T}$ -断片，则称A是$\mathcal{T}$ -端片。

设$e=xy$ 是k-连通图G的边，若将e的两个端点用一个新的顶点代替并使新的顶点与x和y的所有邻点连边所得到的图记为G/e。若G/e还是k-连通图则称e是G的k-可收缩边，否则我们称e是不可收缩边。在不引起混淆的情况下我们简称e是G的可收缩边。若G是k-连通图，e是G的k-可收缩边，则G/e是k-连通图。e是G的k-可收缩边，则G和G/e连通度相同且G/e的顶点数比G的顶点数少。k-可收缩边的存在，使得人们可以用归纳法证明一些图的性质。例如，利用3-连通图一定存在3-可收缩边这一性质，人们利用归纳法证明了著名的krutowski定理。

Theorem 1. 设G是平面图当且仅当G不包含$K_{3,3}$ 或$K_5$ 作为子式。

Figure 1. Contracting edge xy into a vertex

图1. 边xy的收缩

另一方面，由定义可知，若e是G的不可收缩边，则G中存在k-点割T使得e的两个端点都包含在T内。

设e是k-连通图的边，若$G-e$ 还是k-连通图则称e是G的k-可去边，在不引起混淆的情况下简称e是G的可去边。为方便叙述，我们记$G\backslash e=G-e$ 。不存在可去边的k-连通图称为极小k-连通图。若G是极小k-连通图，e是G的一条边，由于$G-e$ 不是k-连通图，则$G-e$ 中存在$k-1$ -点集T使得$G-e-T$ 不连通且$G-e-T$ 恰有两个分支A₁和A₂满足e的两个顶点分别包含在A₁和A₂中。

设G₁和G₂是两个图，$\varphi :V\left(G_1\right)\to V\left(G_2\right)$ 是一一映射，满足uv是G₁的边当且仅当$\varphi \left(u\right)\varphi \left(v\right)$ 是G₂的边。我们称$\varphi$ 是G₁到G₂的同构映射。此时，称G₁与G₂同构，记为$G_1\cong G_2$ 。由定义可知，$G_1\cong G_2$ 表明这两个图本质上是一样的。

设G是k-连通图，H是由G的子图经过去点、去边和收缩边运算得到，我们称H是G的子式。设H和G都是3-连通图且H是G的子式，称边e是H-可去边，如果G\e是3-连通图且包含H作为子式；称边e是H-收缩边，如果G/e是3-连通图且包含H作为子式。设H和G都是3-连通图，H是G的子式且H与G之间不构成同构关系，P.Seymour在1980年证明了，除了一类特殊例外图，G中存在H-可去边或H-可收缩边。

人们对极小k-连通图的结构进行了诸多研究，得到了一系列结论。W.Mader [1]证明了极小k-连通图的每一个圈上至少有一个k-度点，由此他给出了极小k-连通图中k-度点数量的下界。

Theorem 2. [1]设G是一个极小k-连通图，则G中至少有$\frac{\left(k-1\right)n+2k}{2k-1}$ 个k度点，这里的n是图G的顶点个数。

K.Ota [2]等人对极小3-连通图的可收缩边分别进行了研究，N.Dean [3]等人对极小3-连通图最长圈上的可收缩边的数目进行了估计，得到了如下结论：

Theorem 3. [2]设G是一个极小3-连通图且$\left|G\right|\ge 5$ ，则G中至少有$\frac{\left|V\left(G\right)\right|+3t}{2}$ 条可收缩边，这里的t是度大于等于3的顶点个数。

Theorem 4. [3]设G是一个极小3-连通图且$\left|G\right|\ge 7$ ，C是G的最长圈，则C上的可收缩边的数目不小于$\frac{1}{3}\left|E\left(C\right)\right|$ 。

关于极小3-连通图的构造，也已经有了很多的研究。为方便叙述，我们先介绍如下运算：

运算A：设点x和边ab在3-连通图G中不关联，在ab中插入一个点y并连接xy；

运算B：设边ab和边cd是3-连通图G的两条边，在ab和cd中分别插入点x和y并连接xy；

运算C：设点x，y，z是3-连通图G的三个点，在G加入一个新的顶点w并使其和x，y，z都连边。

定义1.设G是连通图，路P称为弦路，如P与某一个圈C的公共部分仅为P中某一条边的两个端点。

定义2.设G是连通图，S是$V\left(G\right)\cup E\left(G\right)$ 的子集，若S满足如下条件之一则称S是3-compatible：

1) $S=\left\{x,ab\right\}$ ，其中x是点，ab是边，$x\notin \left\{a,b\right\}$ 且x-a路和x-b路都不是G-ab中的弦路。

2) $S=\left\{ab,cd\right\}$ ，其中ab和cd是不同边，且a-c路，a-d路，b-c路，b-d路都不是G-ab-cd中的弦路。

3) $S=\left\{x,y,z\right\}$ ，其中x，y，z是不同的顶点且x-y路，y-z路，z-x路都不是G中的弦路。

Robin W.Dawes [4]对极小3-连通图的构造进行了研究，证明了如下定理：

Theorem 5. [4]设H是极小3-连通图，G是对H上的集合S进行运算A或运算B或运算C得到的图，则G是极小3-连通图当且仅当S是3-compatible。

定理1给出了极小3-连通图的构造方式，但是这里必须要验证S是3-compatible，这在实际应用中是不容易做到的。K.Ota等人对曲面上的极小3-连通图进行了研究，给出了这类图的边数的上界。

Theorem 6. [2]设G是阶为n的极小3-连通图，G可嵌入欧拉示性数为$\chi$ 的闭曲面上，则有

$\left|E\left(G\right)\right|\le \{\begin{array}{l}2n-2\chi =2\\ 2n-\chi \chi \le 1\end{array}$

定理2证明的思路是用归纳法，即讨论一个极小3-连通平面图如何通过运算得到更小的极小3-连通图，并且每次这样的运算所减少的边的数目是可以确定的。另一方面，有学者对含有某一个图作为子式的3-连通图的结构进行了研究。

Theorem 7. [5]设G和H是简单3-连通图，H是G的子式且$G\ne W_n$ ，$H\ne W_3$ ，则G存在一条边使得$G^{\prime }=G\backslash e$ 或者$G^{\prime }=G/e$ 是简单3-连通图且H是$G^{\prime }$ 的子式。

Figure 2. Prism

图2. Prism

Theorem 8. [6]设G和H是简单3-连通图，H是G的子式且G不存在H-可去边，则存在图$G^{\prime }$ 使得H是$G^{\prime }$ 子式且$G^{\prime }$ 没有H-可去边，其中$G^{\prime }$ 满足如下条件之一：

1. $G^{\prime }=G/e$ ；(运算一)

2. $G^{\prime }=G\backslash f/e$ ，其中e，f与G的同一个3-度点相关联；(运算二)

3. $G^{\prime }=G-w$ 。(运算三)

Theorem 9. [6]设G是平面图，则如下结论成立：

1. $\left|E\left(G\right)\right|\le 3\left|V\left(G\right)\right|-6$ ，等式成立当且仅当其嵌入平面时每一个面都是三边形。

2. 若G不含三边形，则$\left|E\left(G\right)\right|\le 2\left|V\left(G\right)\right|-4$ ，等式成立当且仅当其嵌入平面时每一个面都是四边形。

Theorem 10. [7]设G是简单3-连通图，则G存在Prism作为子式当且仅当$G\notin \left\{K_5-e,K_5,K_{n-3,3},W_n,{K^{\prime }}_{n-3,3},{K^{″}}_{n-3,3}\right\}$ 。

关于极小3-连通平面图的构造，S. R. Kingan提出了如下问题：

问题1. [6]设G是极小3-连通平面图，且$G\ne W_n$ ，则G是否可以通过一系列运算一和运算二得到prism？

为了叙述方便，我们记满足条件$G\left[V_3\left(G\right)\right]\cong {\overline{K}}_t$ ，$G\left[V_4\left(G\right)\right]\cong {\overline{K}}_t$ 的极小平面3-连通图所组成的图类为$\mathcal{G}$ 。令$C=x_1{y}_1{x}_2{y}_2\cdots x_n{y}_n{x}_1$ 是长为2n的圈，增加点$x_{ii}$ ，使得$x_{ii}$ 与$x_i$ 的邻点都相邻，$i\in \left\{1,2,\cdots ,n\right\}$ 。在此基础上增加点a和b，使得a和x_ii相邻，b和x_i相邻，$i\in \{1,2,\dots ,n\}$ ，我们把最终所得到的图记为G_n。容易验证$G\in \mathcal{G}$ 。令$C_x=x_1{x}_2{x}_3\cdots x_n{x}_1$ ，$C_y=y_1{y}_2{y}_3\cdots y_n{y}_1$ ，$C_z=z_1{z}_2{z}_3\cdots z_n{z}_1$ 都是长为n的圈，其中n为偶数。将z_i与x_i，y_i相连，$i\in \left\{1,2,\cdots ,n\right\}$ 。将所得到的图记为H。对$i\in \left\{1,2,\cdots ,n\right\}$ ，用z_i1和z_i2替代z_i使得z_i1与z_i-1，x_i，y_i相连，z_i2与z_i+1，x_i，y_i相连。我们把最终所得到的图记为H_n。容易验证$H_n\in \mathcal{G}$ 。

我们注意到G_n和H_n中的每一条边收缩后至少还要去掉两条边才能得到极小3-连通图。因此，G_n和H_n不能通过运算一和运算二得到更小的极小3-连通平面图。进一步，由G_n和H_n可知图类$\mathcal{G}$ 中存在无限多个图，这些图不能通过运算一和运算二得到更小的极小3-连通平面图。

本文我们对问题1进行了研究，证明了如下结论：

Theorem 11. 设G是极小3-连通平面图且不是轮图，若G不能通过一系列运算一和运算二得到更小的极小平面3-连通图，则$G\in \mathcal{G}$ 。

2. 主要定理的证明

为证明主要定理，我们需要如下引理。

Lemma 12. [8]设G是一个k-连通图，T_i是一个k-点割，i = 1,2。令A是一个T₁-断片，B是一个T₂-断片。若$B\cap A\ne \varnothing$ ，则$\left|T_2\cap A\right|\ge \left|\overline{B}\cap T_1\right|$ 。

Lemma 13. [8]设G是一个k-连通图，$\mathcal{T}$ 是G满足特定性质的k-点割的集合。假设$T_i\in \mathcal{T}$ ，F_i是一个T_i-断片，i = 1,2。若F₁是一个$\mathcal{T}$ -端片使得$F_1\subseteq F_2$ 但$F_1\ne F_2$ 且$F_1\cap F_2\ne \varnothing$ ，则${\overline{F}}_1\cap {\overline{F}}_2=\varnothing$ ，$F_1\cap F_2$ 不是断片，$\left|T_2\cap F_1\right|>\left|\overline{B}\cap T_1\right|$ 且$\left|\left(T_2\cap F_1\right)\cup \left(T_2\cap T_1\right)\cup {\left(F_2\cap T\right)}_1\right|>k$ 。

Lemma 14. [9]设G是3-连通图，则G中的3度点至少关联一条3-可收缩边。

Lemma 15. [9]设G是极小3-连通图，e是两端点度数都至少为4的边，则e是G的可收缩边。

Lemma 16. [6]设G是极小3-连通图，$e=xy$ 是G的可收缩边，则如下结论成立：

1)若$d\left(x\right)\ge 4$ ，$d\left(y\right)\ge 4$ ，则G/e是极小3-连通图。

2)若$d\left(x\right)=d\left(y\right)=3$ ，则存在边集$F\subseteq E\left(G/e\right)$ 且$\left|F\right|\le 1$ 使得$G/e-F$ 是极小3-连通图。

Lemma 17. [10]设G是极小3-连通图，x是G的3度点。若x与两条不可收缩边关联，则G中有三边形包含x。

由定理10可知如下引理成立：

Lemma 18. 设G是简单3-连通平面图，则G有Prism子式当且仅当$G\notin \left\{W_n,K_5-e\right\}$ 。

由引理18和定理8可得如下引理：

Lemma 19. 设G是极小3-连通平面图且$G\notin \left\{W_n,K_5-e\right\}$ ，则存在极小3-连通图使得$G^{\prime }$ 有Prism子式且满足下列条件之一：

1) $G^{\prime }=G/e$ ；

2) $G^{\prime }=G\backslash f/e$ ，其中e，f与G的同一个3度点关联；

3) $G^{\prime }=G-w$ .

证明：由于G是极小3-连通平面图，故G不存在Prism-可去边。由定理8可知，存在$G^{\prime }$ 使得$G^{\prime }$ 存在Prism子式且满足定理条件。

Lemma 20. 设G是极小3-连通平面图，$xyz$ 是G的三边形，则x，y，z中至少有两个3度点。

证明：假设结论不成立。由G是极小3-连通图可知G的每一个圈上至少有一个3度点。不妨设$d\left(x\right)=3$ 。若$d\left(y\right)\ge 4$ ，$d\left(z\right)\ge 4$ ，则由G为极小3-连通图可知，$G-yz$ 中存在2-点割T使得$G-yz-T$ 的两个分支都至少2个点。记$G-yz-T$ 的两个分支为$H_1$ 和$H_2$ 。显然$x\in T$ 。由对称性，设$y\in H_1$ ，$z\in H_2$ 。由$d\left(x\right)=3$ 可知$\left|N\left(x\right)\cap H_1\right|=1$ 或$\left|N\left(x\right)\cap H_2\right|=1$ 。不妨设$\left|N\left(x\right)\cap H_1\right|=1$ 。于是$T\cup \left\{y\right\}-x$ 是G的2-点割，矛盾。故y或z必有一个点是3度点。引理整毕。

Lemma 21. 设G是极小3-连通平面图且w是G顶点且$N\left(w\right)=\left\{x_1,x_2,x_3\right\}$ ，$d\left(x_i\right)\ge 4$ ，这里$i\in \left\{1,2,3\right\}$ ，则如下结果成立：

1) $G\left[\left\{x_1,x_2,x_3\right\}\right]\cong \overline{K_3}$ ；

2) $\left|E\left(w\right)\cap E_C\left(G\right)\right|\ge 2$ 。

证明：1) 假设结论不成立。不妨设$x_1{x}_2\in E\left(G\right)$ ，于是$x{x}_1{x}_2$ 是三边形。注意到$d\left(x_1\right)\ge 4$ ，$d\left(x_2\right)\ge 4$ ，这与引理20矛盾，故$x_1{x}_2\notin E\left(G\right)$ ，同理可知$x_1{x}_3\notin E\left(G\right)$ ，$x_2{x}_3\notin E\left(G\right)$ 。故$G\left[\left\{x_1,x_2,x_3\right\}\right]\cong \overline{K_3}$ 。

2) 假设$\left|E\left(w\right)\cap E_C\left(G\right)\right|\le 1$ ，则w与2条不可收缩边关联，设$w{x}_1$ 和$w{x}_2$ 是与w关联的不可收缩边。设T为包含$w{x}_1$ 的最小点割，A为$G-T$ 的一个分支。由于$d\left(w\right)=3$ ，可知$\left|N\left(w\right)\cap A\right|=1$ 且$\left|N\left(w\right)\cap \overline{A}\right|=1$ 。此时，不妨设$x_2\in A$ ，$x_3\in \overline{A}$ 。由于$w{x}_2$ 是不可收缩边，故存在最小点割$T_1\supseteq \left\{w,x_2\right\}$ 。设B是$G-T_1$ 的一个分支。

若$A\cap B\ne \varnothing$ ，则由$\left|N\left(w\right)\cap A\right|=1$ 可知$N\left(w\right)\cap B\cap A=\varnothing$ 。于是$\overline{A}\cap \overline{B}=\varnothing$ 。若$A\cap \overline{B}\ne \varnothing$ ，则同理可知$\overline{A}\cap B\ne \varnothing$ 。于是$\overline{A}=\overline{A}\cap T_1$ 。此时可知$\left|\overline{A}\right|=1$ ，即$d\left(x_3\right)=3$ ，矛盾。于是$A\cap \overline{B}=\varnothing$ ，进而$\overline{B}=\overline{B}\cap T$ 。此时，我们易见$x_1\in \overline{B}\cap T$ 。由$d\left(x_1\right)\ge 4$ 可知，$\left|\overline{B}\cap T\right|\ge 2$ 。由于$\left|A\cap T_1\right|>\left|\overline{B}\cap T\right|$ ，可知$\left|A\cap T_1\right|\ge 3$ ，于是$\left|T_1\right|\ge 4$ ，矛盾。所以$A\cap B=\varnothing$ 。

同理，可以证明$A\cap \overline{B}\ne \varnothing$ 。于是$A=A\cap T_1$ 。由$d\left(x_1\right)\ge 4$ ，可知$\left|A\cap T_1\right|\ge 2$ 。故$\overline{A}\cap T_1=\varnothing$ 。

不妨设$A\cap \overline{B}\ne \varnothing$ 。于是$\left|B\cap T\right|\ge 2$ ，故$\overline{B}\cap T=\varnothing$ 。故$\overline{A}\cap \overline{B}=\varnothing$ 。故$\overline{B}=\varnothing$ ，矛盾。引理证毕。

Lemma 22. 设G是极小3-连通平面图，若G中存在三边形，则G可以通过运算一或运算二得到更小的极小平面3-连通图。

证明：设$xyz$ 是G的三边形，由引理20，不妨设$d\left(x\right)=d\left(y\right)=3$ 。设$N\left(x\right)=\left\{y,z,x^{*}\right\}$ ，$N\left(y\right)=\left\{x,z,y^{*}\right\}$ ，易见$x{x}^{*}$ 和$y{y}^{*}$ 都是3-可收缩边。

若$d\left(z\right)=3$ ，设$N\left(z\right)=\left\{y,x,z^{*}\right\}$ 。易见$x{x}^{*}$ 不在三边形内(否则，若$x{x}^{*}$ 在三边形内，则不妨设$x^{*}=y^{*}$ ，于是$\left\{z^{*},x^{*}\right\}$ 是G的2点割，矛盾)。于是，$G/x{x}^{*}$ 是简单3-连通图。若$G/x{x}^{*}$ 不是极小3-连通图，则存在边集F使得$G/x{x}^{*}-F$ 是极小3-连通图。将$x{x}^{*}$ 收缩后得到的点记为$\overline{x{x}^{*}}$ ，则必有F中的边都与$\overline{x{x}^{*}}$ 关联。进一步，由于$d\left(y\right)=d\left(z\right)=3$ ，我们有F中的边都与$x^{*}$ 关联。若$d\left(x^{*}\right)\ge 4$ ，F中存在边e使得$G-e$ 是3-连通，矛盾。所以$d\left(x^{*}\right)=3$ ，于是$d_{G/x{x}^{*}}\left(\overline{x{x}^{*}}\right)=4$ ，故$\left|F\right|\le 1$ 。即G可以通过运算一或运算二得到更小的极小平面3-连通图。

若$d\left(z\right)\ge 4$ ，此时，类似于上面的证明我们可知$x^{*}\ne y^{*}$ 。若$x{x}^{*}$ 在三边形内，必有$x^{*}$ 与$z^{*}$ 相邻。由引理20可知$d\left(x^{*}\right)=3$ ，于是$G/x{x}^{*}-z{x}^{*}$ 是极小3-连通图。即G可以通过运算一或运算二得到更小的极小平面3-连通图。故不妨设若$x{x}^{*}$ 不在三边形内。这里我们分$d\left(x^{*}\right)=3$ 和$d\left(x^{*}\right)\ge 4$ 两种情形讨论。若$d\left(x^{*}\right)=3$ ，则$d_{G/x{x}^{*}}\left(\overline{x{x}^{*}}\right)=4$ ，又由于F中的边都与$\overline{x{x}^{*}}$ 关联。故$\left|F\right|\le 1$ ，即G可以通过运算一或运算二得到更小的极小平面3-连通图。若$d\left(x^{*}\right)\ge 4$ ，由于F中的边都与$\overline{x{x}^{*}}$ 关联，若$\left|F\right|\ge 2$ ，则F中必有一条边，设为e，是与$x^{*}$ 关联的，于是$G-e$ 是3-连通图，矛盾。故$\left|F\right|\le 1$ 并且F中的边一定是与x关联的，即G可以通过运算一或运算二得到更小的极小平面3-连通图。

下面完场定理11的证明。

设G是极小3-连通图且G不能通过运算一或运算二得到更小的极小平面3-连通图。由引理22可知G中不存在三边形。为证明定理11，只需证明如下断言成立。

断言 若$xy\in E\left(G\right)$ ，则$d\left(x\right)=3$ ，$d\left(y\right)\ge 4$ 。

证明：若$d\left(x\right)=d\left(y\right)=3$ ，设$N\left(x\right)=\left\{x_1,x_2,y\right\}$ 。注意到G中不存在三边形，由引理17，x关联至少2条可收缩边。不妨设$x{x}_1$ 是可收缩边，则由G不含三边形可知，$G/x{x}_1$ 是简单3-连通图。由于G不能通过运算一或运算二得到更小的极小平面3-连通图，可知$G/x{x}_1$ 不是极小3-连通图。于是存在边集F使得$G/x{x}_1\backslash F$ 是极小3-连通图。

首先证明F中的边都与$\overline{x{x}_1}$ 关联。否则，设$e\in F$ 且e不与$\overline{x{x}_1}$ 关联，则e是G的边且e不与$\left\{x,x_1\right\}$ 中的点关联。显然，$G/x{x}_1-e$ 是3-连通图且$G/x{x}_1-e\cong \left(G-e\right)/x{x}_1$ 。下面证明$G-e$ 是3-连通图。否则，设$G-e$ 是2-连通图，T是$G-e$ 的2-点割，A是$G-e-T$ 的一个分支。若$\left\{x,x_1\right\}\subseteq T$ ，则$\left(G-e\right)/x{x}_1$ 不是3-连通图，矛盾。若$\left\{x,x_1\right\}\subseteq A$ ，则$\left(G-e\right)/x{x}_1$ 不是3-连通图，矛盾。因此，由对称性，$\left\{x,x_1\right\}\cap A\ne \varnothing$ ，$\left\{x,x_1\right\}\cap T\ne \varnothing$ 。由于e不与$\left\{x,x_1\right\}$ 中的点关联，$\left|A\right|\ge 2$ 。于是，$\left(G-e\right)/x{x}_1$ 不是3-连通图，矛盾。故$G-e$ 是3-连通图，这与G是极小3-连通图矛盾。故F中的边都与$\overline{x{x}_1}$ 关联。

若$d\left(x_1\right)=3$ ，则$d_{G/x{x}_1}\left(\overline{x{x}_1}\right)=4$ ，于是$\left|F\right|=1$ ，即G可以通过运算二得到更小的极小平面3-连通图，矛盾。故不妨设$d\left(x_1\right)\ge 4$ 。若$\left|F\right|=1$ ，则G可以通过运算一得到更小的极小平面3-连通图，矛盾。于是，$\left|F\right|\ge 2$ 。由于$d\left(y\right)=3$ ，则F中存在边e且e不与$x_2$ ，y关联。因此，e是G的边，故e在G中不与$\left\{x_2,y\right\}$ 中的点关联。类似于上面的证明可知$G-e$ 是3-连通图，矛盾。所以，我们有$d\left(x\right)\ge 4$ 或$d\left(y\right)\ge 4$ 。

若$d\left(x\right)\ge 4$ ，$d\left(y\right)\ge 4$ ，则由引理15可知e是可收缩边。于是由引理16可知$G/e$ 是极小3-连通图，矛盾。于是断言成立，引理证毕。

基于图类$\mathcal{G}$ 的构造特征，我们提出如下问题。

问题2. 设$G\in \mathcal{G}$ ，则G是否不能通过一系列运算一和运算二得到阶更小的极小3-连通平面图？

问题3. 设$G\in \mathcal{G}$ 且G通过一系列运算一和运算二得到阶更小的极小3-连通平面图。x是G的任意3度点，则G-x是否为极小3-连通平面图？

如果问题2的答案是肯定的，则可以得到极小3-连通图不能通过一系列运算一和运算二得到阶更小的极小3-连通平面图的充分必要条件，这将会是非常有意义的结论。关于问题3，我们有如下局部的结论。

Theorem 23. 设$G\in \mathcal{G}$ ，则G存在至少6个3度点，使得G去掉其中的每一个点后得到的图都是极小3-连通平面图。

证明：设x是G的3度点且$G-x$ 不再是3-连通图，则存在包含x的3-点割T。我们将G中包含3度点的3-点割的集合记为$\mathcal{T}$ 。

断言1. 设A是G的$\mathcal{T}$ -断片，则$\left|A\right|\ge 4$ 。

证明：设$T=N\left(A\right)$ ，x是包含在T中的3度点。令$x_1\in N\left(x\right)\cap A$ ，于是$d\left(x_1\right)\ge 4$ 。故$\left|A\right|\ge 2$ 且$G\left[A\right]$ 中存在边。若$\left|A\right|=2$ ，则易见G中存在三边形，矛盾。故不妨设$\left|A\right|=3$ 。若A中有2个3度点，则易见$T-x$ 中的点都是度至少为4的点。于是，x₁必然与$T-x$ 中的一个点相邻，即G中存在相邻的度至少为4的两个点，矛盾。若A中含有2个度至少为4的点，则易见$T-x$ 中的点都是3度点。于是，A中的3度点必定与T中的一个点相邻，即G中存在两个相邻的3度点，矛盾。故断言1成立。

断言2. 设A是G的$\mathcal{T}$ -端片，则对A中的任意3度点u都有$G-u$ 是3-连通图。

证明：设A是一个$\mathcal{T}$ -端片。设$T=N\left(A\right)$ ，x是包含在T中的3度点。令$x_1\in N\left(x\right)\cap A$ ，于是$d\left(x_1\right)\ge 4$ 。故$\left|A\right|\ge 4$ 且$G\left[A\right]$ 中存在边，由此可知A中存在3度点。设y是A中的3度点，取T₁为G中包含y的3-点割，B为一个T₁-断片。若$B\cap A\ne \varnothing$ ，则由A是G的$\mathcal{T}$ -端片及引理13可知$B\cap A$ 不是T-断片。于是，我们有$\overline{B}\cap \overline{A}=\varnothing$ 且$\left|A\cap T_1\right|>\left|\overline{B}\cap T\right|$ ，$\left|B\cap T\right|>\left|\overline{A}\cap T_1\right|$ 。此时，若$\overline{B}\cap A\ne \varnothing$ ，则同理可知$B\cap \overline{A}=\varnothing$ ，且$\left|\overline{B}\cap T\right|>\left|\overline{A}\cap T_1\right|$ 。此时，$\overline{A}=\overline{A}\cap T_1$ 。由于$\overline{A}$ 是$\mathcal{T}$ -断片，因此，$\left|\overline{A}\right|\ge 4$ 。于是，$\left|T_1\right|\ge 4$ ，矛盾。故不妨设$\overline{B}\cap A=\varnothing$ ，于是$\overline{B}=\overline{B}\cap T$ 。类似于上面的证明，我们可知$\left|T\right|\ge \left|\overline{B}\right|\ge 4$ 。故$B\cap A=\varnothing$ ，$\overline{B}\cap A=\varnothing$ ，于是$A\subseteq T_1$ ，即$\left|T\right|\ge 4$ ，矛盾。故断言2成立。

断言3. 设A是G的$\mathcal{T}$ -端片，则A中包含至少2个3度点。

证明：设$T=N\left(A\right)$ ，x是包含在T中的3度点。令$x_1\in N\left(x\right)\cap A$ ，于是$d\left(x_1\right)\ge 4$ 。设A恰好包含一个3度点，设为u。此时必有$\left|A\right|=4$ 且T中的点都是3度点。另一方面，注意到T中的每一个点都在A中有3个邻点，即T中的每一个点都在$\overline{A}$ 中没有邻点，矛盾。故A至少包含2个3度点。断言3成立。

断言4. 设A是G的$\mathcal{T}$ -端片，则A中包含至少3个3度点。

证明：用反证法。设A中恰有2个3度点。设$T=N\left(A\right)$ ，x是包含在T中的3度点。我们先证明$\left|A\right|\ge 5$ 。如若不然，设$A=\left\{x_1,x_2,y_1,y_2\right\}$ ，其中$d\left(x_1\right)=d\left(x_2\right)=3$ ，$d\left(y_1\right)\ge 4$ ，$d\left(y_2\right)\ge 4$ 。于是T中至少有2个3度点。设$T=\left\{u_1,u_2,u_3\right\}$ ，其中u₁，u₂是3度点。由$\mathcal{G}$ 的定义可知u₃是度至少为4的点。此时，$G\left[\left\{x_1,x_2,y_1,y_2\right\}\right]\cong K_{2,3}$ 。注意到u₁同时与y₁和y₂相邻。令$H=G-\left\{x_1,x_2,y_1,y_2,u_3\right\}$ ，此时，H是连通图。显然，$G/H\cong K_{3,3}$ 。这与G是平面图矛盾。

于是$\left|A\right|\ge 5$ 。若$\left|A\right|\ge 6$ ，则由A中恰有两个3度点可知A至少有4个度至少为4的点。由此，可知$A\cup T$ 中至少有6个3度点。另一方面，由于A中恰有两个3度点，$A\cup T$ 中至多有5个3度点，矛盾。故不妨设$\left|A\right|=5$ 。

设$A=\left\{x_1,x_2,y_1,y_2,y_3\right\}$ ，其中$d\left(x_1\right)=d\left(x_2\right)=3$ ，$d\left(y_1\right)\ge 4$ ，$d\left(y_2\right)\ge 4$ ，$d\left(y_3\right)\ge 4$ 。于是T中至少有2个3度点。设$T=\left\{u_1,u_2,u_3\right\}$ ，其中$d\left(u_1\right)=3$ ，$d\left(u_2\right)=3$ 。若u₃是度至少为4的点，此时，$G\left[\left\{x_1,x_2,u_1,u_2,y_1,y_2,y_3\right\}\right]\cong K_{4,3}$ ，这与G是平面图矛盾。故不妨设$d\left(u_3\right)=3$ ，于是$G\left[\left\{x_1,x_2,y_1,y_2,y_3\right\}\right]\cong K_{3,3}$ 。此时，$G\left[\left\{u_1,u_2,u_3,y_1,y_2,y_3\right\}\right]$ 是2-正则图，$G\left[\left\{u_1,u_2,u_3,y_1,y_2,y_3\right\}\right]$ 存在完美匹配。令$H=G-\left\{x_1,x_2,y_1,y_2,y_3\right\}$ ，则易见H是连通图。于是，$G/H\cong K_{3,3}$ ，这与G是平面图矛盾。故断言4成立。

下面我们完成定理23的证明。首先，由定义可知G中至少有4个3度点。若G中恰有4个3度点则$G\cong K_{\text{4},3}$ ，这与G是平面图矛盾。故不妨设G至少有6个3度点。若G的每一个3度点去掉后都还是3连通图，则结论成立。故不妨设G存在3度点x使得$G-x$ 不再是3-连通图。我们将G中包含3度点的3-点割的集合记为$\mathcal{T}$ 。由定义可知G存在两个$\mathcal{T}$ -端片，由断言2和断言4可知定理23成立。