大数据和云计算的应用快速推动社会的发展，改善和提高了人类生活水平.图论是数学中的一个分支，由于在表述各种关系时它具有强大的能力和高效的算法，因而它在大数据分析中被广泛运用.无论是图论的理论研究，还是被广泛应用于互联网领域的图染色以及标号模型^[1-6]，都是以图的结构为基础的.因而图的结构问题被许多专家认为是图论研究的核心问题.对于图结构的研究，首先是结构的存在性问题.

一个图被称为1-平面图当且仅当它可以画在一个平面上，使得它的任何一条边最多交叉另外一条边. 1-平面图的结构比平面图复杂，得到的结果相对较少.为了方便研究，1-平面图被一些学者分出两个子类，即IC-平面图与NIC-平面图. NIC-平面图的概念是由文献[7-8]提出的.

最早研究轻子图存在性的学者是Kotzig，他于1955年在文献[9]中证明了：任意的3-连通平面图包含一条边，且与这条边所关联的两顶点的度之和至多为13.但是轻子图的概念却是由文献[10]给出的.对于1-平面图中轻子图的研究十分有限.文献[11]证明了：每个3-连通的1-平面图含有一条轻边，且轻边的高度的上界为20；最小度至少为6的1-平面图包含一个3-圈uvw且max{d(u)，d(v)，d(w)}≤10.文献[12]证明了：最小度至少为6的1-平面图包含一个4-圈，且4-圈上的点的度至多为47.文献[13]证明了：在最小度至少为5并且最小边度至少为12的1-平面图类中存在轻3-圈，且3-圈上的点的度至少为7至多为20.对于NIC-平面图中子图的存在性问题^[13]，文献[14]证明了：最小度至少为5的NIC-平面图包含一个轻3-圈，且3-圈上的点的度数至多为26.

本文只考虑简单的有限无向图.设G是一个平面图，分别用V(G)，E(G)，F(G)，Δ(G)，δ(G)来表示它的点集合、边集合、面集合、最大度和最小度^[15].与点u关联的边的条数为点u的度，记为d(u).

G中任意一条边uv所关联的点u，v的度的和d(u)+d(v)称之为边uv的度^[15].用k-，k⁺-和k^--点或面分别表示一个点或面的度为k，至少为k和至多为k.将K_1，3中任意两点连接起来所形成的图形称为风筝.其余文中未标注出处的定义，参考文献[15].

本文用权转移方法证明每个最小度至少为5并且最小边度至少为11的NIC-平面图中存在轻风筝且风筝上的点的度数至多为29.

定义 1^[7-8]  在1-平面图G中，c₁，c₂是G中的两个交叉点，若满足|S(c₁)∩S(c₂)|≤1，则称G为NIC-平面图.

定义 2^[7-8]  设G是NIC-平面图.如果将G中的所有交叉点全部看成是4度点，则可得到一个交叉数为0的图G^×，称图G^×为G的关联图.设v是图G^×中的一个点，如果v∈V(G^×)\V(G)，则称v是G^×的假点，或称v是G的交叉点.如果图G^×的一个面f关联至少一个假点，则称f为G^×的假面，否则称f为G^×的真面.设v是G^×中的k-点，v₁，v₂，…，v_k是v在G^×中按顺时针排列的所有邻点.在G^×中与边vv_i和vv_i+1关联的面记为f_i，其中1≤i≤k，并记v_k+1=v₁.

定义 3^{[11, 13]}   设H是连通图，Ĝ是图类，如果任意的G∈Ĝ，G包含子图K，K同构于图H，且满足$\underset{x\in V\left( K \right)}{\mathop{\text{max}}}\, \left\{ {{d}_{(G)}}\left( x \right) \right\}\le {{t}_{h}}<\infty $或$\sum\limits_{x\in V\left( K \right)}{\left\{ {{d}_{(G)}}\left( x \right) \right\}\le {{t}_{w}}<\infty }$，那么称H为Ĝ的轻子图，若t_h是满足$\underset{x\in V\left( K \right)}{\mathop{\text{max}}}\, \left\{ {{d}_{(G)}}\left( x \right) \right\}\le {{t}_{h}}<\infty $的最小整数，则称t_h为H在图类Ĝ中的高度.

定理 1  每个最小度至少为5并且最小边度至少为11的NIC-平面图含有一个风筝K₃⁺，且

证   用反证法来证明定理1.假设定理1不真，那么存在一个反例G^×，G^×是G的关联图.它所含有的任意一个风筝K₃⁺满足max{d(v₁)，d(v₂)，d(v₃)，d(v₄)}>30.

给G^×中的每个点v赋初始权值为c(v)=d(v)-6，同时给G^×中的每个面f赋初始权值为c(f)=2d(f)-6，利用平面图G^×上的欧拉公式，得出

下面将对V(G^×)∪F(G^×)上的所有元素按下列规则重新分配权值：

(R1) 设f=xyz是G^×中的3-面，且x是30⁺-点.

(R1.1)若y是4-点，xy∈E(G)，则x向y转移$\frac{2}{3}$；特别地，xy关联两个3-面，则x向y转移1.

(R1.2)若y是5-点，则x向y转移$\frac{1}{3}$.

(R1.3)若f是真3-面，且yz关联另一个3-面f′=yzs，其中s是假4-点，则x通过边yz向s转移$\frac{1}{2}$.

(R1.4)若f是假3-面，且y是假4-点，yz关联另一个3-面f′=yzs，其中s是5-点，则x通过边yz向s转移$\frac{1}{6}$.

(R2) 设f是G^×中的4⁺-面.

(R2.1) f向它关联的假4-点转移$\frac{2}{3}$，向它关联的5-点转移$\frac{1}{3}$.

(R2.2)若f的某条边xy关联3-面f′=xys，且s是4-点，则f通过xy向s转移$\frac{1}{3}$.

(R2.3)若f的某条边xy关联3-面f′=xys，且s是5-点，则f通过xy向s转移$\frac{1}{6}$.

设c′(x)为元素V(G^×)∪F(G^×)在应用以上权转移规则后得到的新权值，下面证明对于每个x∈V(G^×)∪F(G^×)，都有c′(x)≥0.因此

这是一个矛盾.

首先，验证对于任意的f∈F(G^×)，有c′(f)≥0.

若d(f)=3，则由(R1)和(R2)知c′(f)=c(f)=0.

若d(f)=4，则由NIC-平面图的定义可知面f至多关联1个假4-点.若面f关联假4-点v₁，其余点分别记为v₂，v₃，v₄，由最小边度至少为11知，此时面f关联至多2个5-点，此时(R2.2)作用面f 2次，再结合(R2.1)得

若面f不关联假4-点，由任意一条K₃⁺含有1个大点知，此时面f至少关联2个大点.若这2个大点相邻，则规则(R2.3)作用于面f 1次，再结合(R2.1)得

若这2个大点不相邻，则此时规则(R2.3)作用于面f 2次，再结合(R2.1)得

若面f关联3个大点，则此时规则(R2.3)作用于面f 3次，再结合(R2.1)得

若面f关联4个大点，则此时规则(R2.3)作用于面f 4次，再结合(R2.1)得

若d(f)=5，则由NIC-平面图的定义可知面f至多关联2个假4-点.若面f关联2个假4-点v₁，v₃，则此时边v₁v₂，v₂v₃，v₃v₄，v₅v₁除了关联面f外分别还关联含有真4-点的3-面，边v₄v₅除了关联面f外还关联含有假4-点的3-面.由任意一条K₃⁺含有20⁺-点知，v₂和v₄是20⁺-点.因此(R2.2)与(R2.3)共作用于面f 5次，再结合(R2.1)得

若面f不关联假4-点，则由任意一条K₃⁺含有30⁺-点知，面f至少关联2个20⁺-点，且这2个点不相邻.面f的外部面中有至多5个假3-面，或2个假3-面和3个真3-面，因此规则(R2.3)最多作用于面f 5次，再结合(R2.1)得

若d(f)≥6，则由NIC-平面图的定义可知面f最多关联$\left\lfloor \frac{1}{2}d\left( f \right) \right\rfloor $个假4-点.若面f关联假4-点，那么至多再关联$\left\lfloor \frac{2}{3}\left( d\left( f \right)-\left\lfloor \frac{1}{2}d\left( f \right) \right\rfloor \right) \right\rfloor $个真4-点，因此由规则(R2.1)，(R2.2)，(R2.3)可知

若面f不关联假4-点，那么至多关联d(f)个真4-点，因此由规则(R2.1)，(R2.2)，(R2.3)可知

接下来，验证对于任意的v∈V(G^×)有c′(v)≥0.

由规则(R1)，(R2)知，图G^×中的度数大于等于6且小于等于29的点不参与权转移，从而当6≤d(v)≤29时，有c′(v)=d(v)-6≥0

因此，只考虑以下3种情况：

情况 1   d(v)=4.

情况 1.1   设v是真4-点.

情况 1.1.1  60;若v至少关联3个4⁺-面，由(R2.1)知f₁，f₂，f₃，f₄分别向v转移$\frac{2}{3}$，因此

情况 1.1.2   若v关联2个4⁺-面，分为如下情况讨论：

当2个4⁺-面相邻时，不妨设其为f₁，f₂.由于G^×是一个反例，v₁，v₂，v₃，v₄中至少有1个点是30⁺-点.

若v₁或v₃是30⁺-点，由(R1.1)知v₁或v₃向v转移$\frac{2}{3}$，由(R2.1)知f₁，f₂分别向v转移$\frac{2}{3}$，故

若v₄是30⁺-点，由(R1.1)知v₄向v转移1，由(R2.1)知f₁，f₂分别向v转移$\frac{2}{3}$，故

若v₂是30⁺-点，则此时：与v₁v₄关联的另外一个面要么是4⁺-面，要么是3-面f′=v₁v₄u，其中u为30⁺-点；与v₃v₄关联的另外一个面要么是4⁺-面，要么是3-面f′=v₃v₄w，其中w为30⁺-点.从而由(R1.3)可知w和u分别向v转移$\frac{1}{2}$，由(R2.2)可知v₁v₄关联的假4⁺-面和v₃v₄关联的4⁺-面分别向v转移$\frac{1}{2}$，由(R1.1)知v₂不向v转值，由(R2.1)知f₁，f₂分别向v转移$\frac{2}{3}$，故

当2个4⁺-面不相邻时，不妨设其为f₁，f₃.若边v₁v₄和边v₂v₃关联的另外一个面均是4⁺-面，则不存在轻风筝.

若边v₁v₄关联的另一个面是3-面，v₂v₃关联的另外一个面是4⁺-面，此时与v₁v₄关联的3-面f′=v₁v₄u，其中u为30⁺-点.由(R1.3)可知u向v转移$\frac{1}{2}$，由(R2.2)可知v₂v₃关联的4⁺-面向v转移12，由(R2.1)知f₁，f₂分别向v转移$\frac{1}{2}$，故

若边v₁v₄关联的另一个面是4⁺-面，v₂v₃关联的另外一个面是3-面，情况与此相同.

若边v₁v₄和v₂v₃关联的另一个面均是3-面，则与v₁v₄关联的3-面记为f′=v₁v₄u，其中u为30⁺-点.由(R1.3)可知u通过v₁v₄向v转移$\frac{1}{2}$.

同理，w通过v₂v₃向v转移$\frac{1}{2}$，由(R2.1)知f₁，f₂分别向v转移$\frac{2}{3}$，故

情况 1.1.3   若v仅关联一个4⁺-面，不妨设其为f₁，则f₂，f₃与f₄均为3-面.

由于图G不含轻K₃⁺，则v₁，v₂，v₃，v₄中至少有1个点是30⁺-点.若v₁是30⁺-点，则此时：与v₁v₄关联的另外一个面要么是4⁺-面，要么是3-面f′=v₁v₄u，其中u为30⁺-点；与v₃v₄关联的另外一个面要么是4⁺-面，要么是3-面f′=v₃v₄w，其中w为30⁺-点.从而由(R1.1)知v₁向v转移$\frac{2}{3}$，由(R1.3)可知u和w分别向v转移$\frac{1}{2}$，由(R2.2)可知v₁v₄关联的假4⁺-面和v₃v₄联的4⁺-面分别向v转移$\frac{1}{2}$，由(R2.1)知f₁向v转移$\frac{2}{3}$，故

由对称性知，v₂是30⁺-点时与此情况相同.

若v₃是30⁺-点，则此时与v₂v₃关联的另外一个面要么是4⁺-面，要么是3-面f′=v₂v₃w，其中w为30⁺-点.由(R1.1)知v₃向v转移1，从而由(R1.3)可知w向v转移$\frac{1}{2}$，由(R2.2)可知v₂v₃关联的假4⁺-面向v转移$\frac{1}{2}$，故

由对称性知，v₄是30⁺-点时与此情况相同.

情况 1.1.4   若v仅关联3-面，即f₁，f₂，f₃与f₄均为3-面，由于G^×是一个反例，v₁，v₂，v₃，v₄中至少有1个30⁺-点，不妨设为v₁，由(R1.1)知v₃向v转移1.而此时与v₂v₃关联的另外一个面要么是4⁺-面，要么是3-面f′=v₂v₃w，其中w为30⁺-点.由(R1.3)可知w向v转移$\frac{1}{2}$.由(R2.2)可知v₂v₃关联的假4⁺-面向v转移$\frac{1}{2}$.因此

情况 2   d(v)=5.

情况 2.1   若v至少关联2个4⁺-面，有如下两种情况：

当2个4⁺-面相邻时，不妨设其为f₁，f₂.

如果f₁，f₂都是4-面.由G的NIC-平面性可知v₁，v₂，v₃，v₄中至少有2个点是假4-点.若恰好有2个点是假4-点，则v₁，v₃或v₂，v₄，或v₂，v₅即是.设v₁，v₃是假4-点.由G^×是一个反例知，v₂，v₄，v₅中有一个30⁺-点.若v₄或v₅是30⁺-点，则根据(R1.2)与(R2.1)，有

由于对称性知，当v₂，v₅是假4-点时，情况与此相同.

如果f₁，f₂中至少有1个5⁺-面.由G的NIC-平面性可知v₁，v₂，v₃，v₄中至多有2个点是假4-点.若恰好有2个点是假4-点，则v₁，v₃，或v₂，v₄，或v₂，v₅，或v₁，v₂即是.设v₁，v₂是假4-点.由G^×是一个反例知，v₂，v₄，v₅中有一个30⁺-点.因此根据(R1.2)与(R2.1)，有

v₁，v₃，或v₂，v₄，或v₂，v₅是假4-点的情况与f₁，f₂都是4-面相同.

如果f₁，f₂都是5⁺-面.由G的NIC-平面性可知v₁，v₂，v₃，v₄中至多有3个点是假4-点.由G^×是反例知v₄，v₅中有一个30⁺-点.因此根据(R1.2)与(R2.1)，有

否则：与v₁v₅关联的另外一个面要么是4⁺-面，要么是3-面f′=v₁v₄u，其中u为30⁺-点；与v₃v₄关联的另外一个面要么是4⁺-面，要么是3-面f′=v₃v₄w，其中w为30⁺-点.由(R1.4)可知w和u分别向v转移$\frac{1}{6}$，由(R2.3)可知v₃v₄关联的4⁺-面和v₁v₅关联的假4⁺-面分别向v转移$\frac{1}{6}$，由(R2.1)知f₁，f₂分别向v转移$\frac{1}{3}$，故

当2个4⁺-面不相邻时，不妨设其为f₁，f₃.如果f₁，f₂都是4-面.由G的NIC-平面性可知v₁，v₂，v₃，v₄中至少有2个点是假4-点.若恰好有2个点是假4-点，则v₁，v₃，或v₂，v₄，或v₂，v₅即是.设v₁，v₃是假4-点.由G^×是反例知v₂，v₄，v₅中有一个30⁺-点，因而v₄或v₅是30⁺-点.因此根据(R1.2)与(R2.1)，有

如果f₁，f₂中至少有1个5⁺-面，由G的NIC-平面性可知v₁，v₂，v₃，v₄中至多有2个点是假4-点.若恰好有2个点是假4-点，则v₁，v₃，或v₂，v₄，或v₂，v₅，或v₁，v₂即是.设v₁，v₂是假4-点，由G^×是反例知v₂，v₄，v₅中有一个30⁺-点.因此根据(R1.2)与(R2.1)，有

v₁，v₃，或v₂，v₄，或v₂，v₅是假4-点的情况与f₁，f₂都是4-面相同.

如果f₁，f₂都是5⁺-面.情况与f₁，f₂中至少有1个5⁺-面的情况相同.

情况 2.2   若v仅关联1个4⁺-面，不妨设其为f₁，则f₂，f₃，f₄与f₅均为3-面.若d(f₁)=4，由G的NIC-平面性可知v至多相邻2个v₁，v₃假4-点.

若v相邻2个假4-点，这2个假4-点要么是v₁，v₃，要么是v₂，v₅.不妨设为v₁，v₃.由于G^×是反例，v₂，v₄，v₅中有一个30⁺-点.

如果v₂是30⁺-点，那么：与v₁v₅关联的另外一个面要么是4⁺-面，要么是3-面f′=v₁v₄u，其中u为30⁺-点；与v₃v₄关联的另外一个面要么是4⁺-面，要么是3-面f′=v₃v₄w，其中w为30⁺-点.从而由(R1.4)可知w和u分别向v转移$\frac{1}{6}$，由(R2.3)可知v₃v₄关联的4⁺-面和v₁v₅关联的假4⁺-面分别向v转移$\frac{1}{6}$，由(R1.2)知v₂向v转移$\frac{1}{3}$，由(R2.1)知f₁向v转移$\frac{1}{3}$，故

v₂或v₅是30⁺-点的情况与此类似.

若v仅相邻1个假4-点，则由G的NIC-平面性可知它是v₄，由于G^×是反例，v₁，v₂，v₃与v₅中有2个30⁺-点.因此根据(R1.3)与(R2.3)，有

若d(f₁)=5⁺，由G的NIC-平面性可知，v至多相邻2个假4-点.

若v相邻2个假4-点，这2个假4-点要么是v₁，v₃，要么是v₂，v₅，要么是v₁，v₂.若这2个假4-点是v₁，v₃，或v₂，v₅，情况与d(f₁)=4时相同，现在讨论这两个假4-点是v₁，v₂的情况.由于G^×是反例，则v₃，v₄与v₅中至少有1个30⁺-点，不妨设为v₄，此时：与v₁v₅关联的另外一个面要么是4⁺-面，要么是3-面f′=v₁v₄u，其中u为30⁺-点；与v₂v₃关联的另外一个面要么是4⁺-面，要么是3-面f′=v₃v₄w，其中w为30⁺-点.由(R1.4)可知w和u分别向v转移$\frac{1}{6}$，由(R2.3)可知v₂v₃关联的4⁺-面和v₁v₅关联的假4⁺-面分别向v转移$\frac{1}{6}$，由(R1.2)知v₂向v转移$\frac{1}{3}$，由(R2.1)知f₁向v转移$\frac{1}{3}$，故

情况 2.3   若v关联3-面，由G的NIC-平面性可知v₁，v₂，v₃，v₄与v₅中至多有1个假4-点，不妨设为v₄，由G^×是反例知，剩余的4个点中至少有2个30⁺-点，不妨设为v₁，v₂.此时：与v₄v₅关联的另外一个面要么是4⁺-面，要么是3-面f′=v₄v₅u，其中u为30⁺-点；与v₃v₄关联的另外一个面要么是4⁺-面，要么是3-面f′=v₃v₄w，其中w为30⁺-点.由(R1.4)可知w和u分别向v转移$\frac{1}{6}$，由(R2.3)可知v₃v₄关联的4⁺-面和v₄v₅关联的假4⁺-面分别向v转移$\frac{1}{6}$，由(R1.2)知v₂向v转移$\frac{1}{3}$，由(R2.1)知f₁向v转移$\frac{1}{3}$，故

情况 3   d≥30.

不妨设f_i1，f_i1+1，...，f_i1+t1-1，f_i2，f_i2+1，…，f_i2+t2-1，...，f_ik，f_ik+1，…，f_ik+tk-1为与v关联的所有3-面(它们在v的周围按顺时针排列)，其中当k≥2时，对于所有的1≤s≤k-1，f_is+ts-1与f_is+1不相邻，并且f_ik+tk-1与f_i1亦不相邻.注意，我们是在模d的意义下进行上述下标中的加法运算的，并且当k=1时，f_i1+t1-1与f_i1可能相邻(此时与v关联的面全部都是3-面).显然，有

情况 3.1   若v仅关联3-面，则由图G不含K₃⁺可知，在v_i1，v_i1+1，...，v_i1+t1中至多有$\left\lfloor \frac{{{t}_{1}}+{{i}_{1}}}{3} \right\rfloor $(或写成$\left\lfloor \frac{d\left( v \right)}{3} \right\rfloor $)个4-点和$\left\lfloor \frac{1}{2}\left( d\left( v \right)-\left\lfloor \frac{d\left( v \right)}{3} \right\rfloor \right) \right\rfloor $个5-点.另外依据NIC-平面图的定义，v通过边v_i1v_i1+1，v_i1+1v_i1+2，...，v_i1+t1-1v_i1+t1，最多向$\left\lceil \frac{{{i}_{1}}+{{t}_{1}}}{3} \right\rceil $(或写成$\left\lceil \frac{d\left( v \right)}{3} \right\rceil $)个假4-点转移权值，最多向$\left\lceil d\left( v \right)-\left\lceil \frac{d\left( v \right)}{3} \right\rceil \right\rceil $个5-点转移权值.按照规则(R1.1)，(R1.2)，(R1.3)和(R1.4)有

情况 3.2   若v既关联3-面又关联4⁺-面，则由图G不含轻风筝可知，对于所有的1≤s≤k，在v_is，v_is+1，...，v_is+ts中至多有$\left\lceil \frac{{{i}_{s}}+{{t}_{s}}}{3} \right\rceil $个假4-点，有$\left\lfloor \frac{1}{2}\left( d\left( v \right)-\left\lceil \frac{{{i}_{s}}+{{t}_{s}}}{3} \right\rceil \right) \right\rfloor $个5-点.另外由NIC-平面图的定义，v通过边v_isv_is+1，v_is+1v_is+2，...，v_is+ts-1v_is+ts，最多向$\left\lceil \frac{{{i}_{s}}+{{t}_{s}}}{3} \right\rceil $个4-点转移权值，最多向$\left\lceil d\left( v \right)-\left\lfloor \frac{{{i}_{s}}+{{t}_{s}}}{3} \right\rfloor \right\rceil $个5-点转移权值.按照规则(R1.1)，(R1.2)，(R1.3)和(R1.4)有

由此得出最小度至少为5并且最小边度至少为11的NIC平面图是成立的，且NIC-平面图含有一个风筝，其最大度至多为29.