(湖南师范大学 数学与统计学院，长沙，410081)

1 引言

本文仅考虑简单、无向、连通和有限的图G,分别有边集E(G)和顶点集V(G).以G-{vi}(1≤i≤n)表示从G中去掉顶点vi后得到的子图，dG(vi)表示G中vi的度(可简写为d(vi))，nj(1≤j≤n-1)表示图G中度为j的顶点个数，N(v)表示顶点v的邻点集，Pn表示有n个顶点的路，G1和G2的联图G1∨G2表示G1和G2中各顶点互相连接后所得到的图，符号[a]表示对a取小于等于a的最大整数.在文献[1]中提到，若平面图G的所有点都在外部区域上，则称此平面图G是外平面图;若外平面图G不能再加上边而不失去外平面性，则称此外平面图G为极大外平面图.我们把外部区域的边界称为界环.显然界环是一个圈，用Cn=(v1,v2,…,vn)来表示，圈Cn上的点下标连续且v1与vn相邻.易见，极大外平面图有2n-3条边(n≥3).没有提到的定义、术语请参见文献[1].

2 预备知识

图

当n=3,4,5时，只有一个非同构的极大外平面图，当n=6时，有三个非同构的极大外平面图, 具体见图2.

图2 n≤6的极大外平面图

下面先介绍极大外平面图的有关性质.

引理2[1]设G是有n个顶点的外平面图(n≥3),那么G为极大外平面图的充要条件是在G的边界Cn内的所有区域均为三角形.

引理4[10]设G是有n个顶点的极大外平面图(n>3),则G的任意两个二度顶点不能相邻.当n=3时，极大外平面图是一个三角形，此时三个顶点彼此相邻且度为2.

由极大外平面图的定义我们易得下面结论.

引理5设G是有n个顶点的极大外平面图(n≥3),则图G界环上的每条边只能存在于一个三角形中.

引理6设G是有n个顶点的极大外平面图(n≥3),且n2=2,则有n3≥2.

证明由极大外平面图的……