 Advances in Applied Mathematics 应用数学进展, 2013, 2, 186-190 http://dx.doi.org/10.12677/aam.2013.24025 Published Online November 2013 (http://www.hanspub.org/journal/aam.html) Minimal Nontoroidal Graphs on Eight Vertices* Fugang Chao, Han Ren Department of Mathematics, East China Normal University, Shanghai Email: chaofugang@126.com, hren@math.ecnu.edu.cn Received: Jun. 28th, 2013; revised: Jul. 30th, 2013; accepted: Aug. 10th, 2013 Copyright © 2013 Fugang Chao, Han Ren. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: Using the technique of embedding, we prove that the graphs obtained from 8 K , the complete graph on eight vertices, by deleting the edges of 3 K , a triangle, or 2,3 K , the complete bipartite graph with 2 vertices and 3 vertices, or 223 K KP, the disjoint union of two paths of length one and one path of length two, are minimal nontoroidal graphs. Keywords: Embedding; Genus; Minimal Nontoroidal Graph 八个点的极小非环面图* 晁福刚，任 韩 华东师范大学数学系，上海 Email: chaofugang@126.com, hren@math.ecnu.edu.cn 收稿日期：2013 年6月28 日；修回日期：2013 年7月30 日；录用日期：2013 年8月10 日 摘 要：借助于嵌入的技巧，证明了由 8 K ，八个点的完全图，去掉3 K ，三角形，或2,3 K ，部集的点数 为2和3的完全二部图，或 223 K KP，长度为 1的两条路和长度为 2的一条路的不交并，中的边 得到的图是极小的非环面图。 关键词：嵌入；亏格；极小非环面图 1. 引言 图G是由有限的点集 VG和称之为边的无序的点对的集合 EG构成。如果边 xy 表现，我们称 x和y 相邻或者相连，x和y是邻点。点 x的度是指其邻点的数目，记作 dx。如果所有的点的度数都是 r，那么 G 是r-正则的。如果H是G的一个子图，称 GH 是H的诱导子图，它是由 H及G中连接 H的两个点的所有 边组成。我们定义 GH 。如果 v是图 G中的一个点，那么或 GVGVH Nv是G的由 v的邻点诱 导的子图。 图G中的一条迹是指一个点的序 12 n x xx，使得 i x 和1i x 是邻点对 1,2,,1in 1n 成立。如果所有的点是 不同的，称这条迹为一条路或一条 n路，记作 。n-圈是由 添加 n Pn Cn P x x得到的。如果 C是图中的一个圈， e是连结 C两个不连续点的边，那么 e是C的一条弦。G中的一个圈 C是一个 Hamilton圈，如果 VC VG。 n K 是n个点的完全图；也就是说，n K 的所有点的度数是 1n 。 曲面 S是一个没有边界的、紧的、连通的 2-维流形。曲面分类定理[1]告诉我们：每个曲面或者同胚于 g S， *资助信息：国家自然科学基金项目(11171114)。 Open Access 186  晁福刚，任 韩 八个点的极小非环面图 添加了g个手柄的球，或者同胚于，添加了 k个叉帽的球。当 k N g SS 时，曲面S的Euler 亏格为 2 g ， 当时，曲面 S的Euler亏格为 k SNk 。特别地， 0 SN 0 是球，是环面，是射影平面，是克莱因 瓶。同胚于一个由平面上的三角形粘贴得到的一个曲面。记n、e、f分别为图 G的边数、点数和面数，经 典的 Euler 公式告诉我们： 1 S1 N2 N 1 S 2fne ，其中 为图 G的Euler 亏格。 曲面 S上的一个嵌入图是嵌入到S上的一个图，使得所有的边，除了一个共同点，都是不交的多边形的 弧。和点 v关联的边构成它的一个顺时针序。嵌入图的一个面是这个曲面的弧连通分支减去这个图。我们假 定每个面同胚于一个圆盘。一个面迹是由在每个点严格向左拐得到的。如果这个迹长度为 k，我们说这是一个 k-面。一个面圈是一个圈同时也是一个面迹。如果 G是嵌入到 上的图，H是G的一个子图，那么 H也可以 嵌入到上。我们称之为诱导嵌入。如果 C是H的一个以同胚于一个圆盘的面为边界的一个面迹，那么这个 面是 C的内部，记作 ，或仅记作 1 S 1 S ,CHint extint C。外部 ,CH 可以类似地定义。G的在 内的点 也说成在 C的内部。如果 C是G的分离成不同分支的圈，其中之一同胚于一个圆盘，那么 C是可收缩的。 否则，C是不可收缩的。一个三角剖分是指一个嵌入图使得每个面以一个三角形为边界3-圈。一个平面的近 三角剖分图是指平面上的一个图，使得每个面，除了可能的一个外面，都以一个 3-圈为边界。外面以一个圈 为边界，也就是外圈。一个图是平面的，或环面的，如果它分别可以嵌入到 或上。 ,CH int 1 S 0 S1 S 称一个图 G是极小非环面的，如果它不能嵌入到环面上，但任意去掉它的一条边后，就可以嵌入到环面 上。在这里，我们借助于嵌入的技巧，先将 7 K 嵌入到环面 上，然后去掉一些边，在一个很小的范围内改动 原来的嵌入方式，再添加一些点和这个点与其它点之间的边，使得新图也可以嵌入到环面 上。 1 S 1 S 本文研究的图都是简单连通无向图，所有的专业术语均可参考文献[2]。 2. 主要定理及其证明 图G的一个剖分图是指把 G的边进行一系列的剖分而得到的一个图。经典的 Kuratowski[3]定理告诉我们： 一个图是平面图当且仅当它不包含 5 K 3,3 K 5 K 或的剖分图。事实上，去掉或3,3 K 的任意一条边，都可以把得到的 图嵌入到平面上，所以 5 K 和3,3 K 是极小的非平面图。一个自然而然的问题是，极小的非环面图有什么样的刻画。 我们的主要结果给出了一类极小非环面图的构造方法。先来看两个曲面拓扑学中的简单的观察结果。 命题 1.1：如果一个图 G嵌入到一个固定的曲面 S上，那么 G一定与 S上的每条不可收缩的闭曲线(不可收 缩圈)有交点。 命题 1.2：如果一个图 G的子图 H可以嵌入到一个固定的曲面 S上，那么 G也可以嵌入到曲面 S上。 在平面图的四色猜想还有解决的时候，数学家为了 研究这个猜想，对曲面 嵌入图的色数进行了探究 。 Heawood[4]证明了：如果 S不是球，那么嵌入到 S上的每个图至多使用 17241 2 h 种不同的颜色， 其中 为S的Euler 亏格。Ringel 和Youngs[5]证明了这个结果对除了克莱因瓶以外的所有曲面都是最好可能的。 嵌入到克莱因瓶上的图仅需6种颜色，而 Heawood 的界告诉我们克莱因瓶上的嵌入图的最大色数为7，这个结 果是由 Franklin[6]得到的。作为地图染色定理的一个副产品，Ringel[7]得到了下述定理所描述的完全图的亏格计 算公式。 34 命题 1.3：如果 n，那么312 nn n gK ，其中 n g Kn K 为完全图 的可定向亏格。如果且 ，那么 3n 7 n 34 6 nn n gK ，其中 g G 为完全图 的不可定向亏格。 n K 由上面的公式，我们可以知道，完全图 8 K 的可定向亏格为 2。在下面定理的证明中，我们会数次使用这个 基本的事实。另外，我们的证明还借助于完全图 7 K 在环面 1 S上的嵌入。下面的图1给出了完全图 7 K 在环面 1 S 的一种嵌入方式。 Open Access 187  晁福刚，任 韩 八个点的极小非环面图 Figure1. Embedding of K7 on the torus 图1. K7在环面上嵌入 定理 1.4：图 、、 18 GKK 3,3282 GKK 38 223 GK KKP 是八个点的极小的非环面图。 证明：考虑图 ，其中 18 GKK 33 K 是一个三角形。我们断言 183 2gGgK K 。这是因为 ，由命题 1.2和命题 1.3知， 183 GKK K 8 8 2 183 gGgK KgK 22g 23efne 22f g 。记 n，e，f分别为图 G的点数、 边数和面数，Euler 公式告诉我们： ne ，其中 g为图G的亏格。因为嵌入是 2-胞腔的，所以有 ， 等号成立当且仅当这个嵌入是一个三角剖分嵌入。将 代入 f 23ef ，可以推出 。 将 、代入上式得，66 ，即 366gen 8n25e gG K 183 7Kg 183 2KgG gK 18 ，所以 G不能嵌 入到环面 上。 3 KK 1 S 下证再去掉83 K K中的任意一条边e，得到的图 '183 GKK e有一个环面嵌入。图 '183 GKK e有 24 条边，由环面上的Euler 公式 ，得 f = 16，所以有0ne f23ef ，它是环面上的一个三角剖分图。去掉 这24 条边中的任意一条，在同构的意义下，仅有两种可能，一种是去掉与这个三角形相关联的一条边，另一种 是去掉与这个三角形不相关联的一条边。仅需给出 '183 GKK e在环面上的一种嵌入方式。以下分两种情 况讨论。 情形 1：如果去掉的是三角形和与这个三角形关联的一条边。先将 7 K 嵌入到环面上，如图1所示。将点 放到面中。不妨设去掉的边为，这样就形成了一个 7面。连接 ，就得到了 8 v 235 vvv 2 83 ,,vv 23 35 5224 ,,,vvvv vv vv14563721 vvvvvvvv 81884 85 86 87 ,,,,vv vvvvvvvvvv e '183 GKK在环面上的一种嵌入，其中 e是 关联的一条 边。 235 vvv 情形 2：如果去掉的是三角形和与这个三角形不相关联的一条边。先将 7 K 嵌入到环面上，如图 1所示。将 点放到面中。不妨设去掉的边为，这样就形成了一个 6面。连接 。改变 的嵌入方式，将连接到。具体方法如下：将边 改为由左边ga 中 间的一点出来，由右边 ga中间的一点进入，由下边da 中间的一点出来，再由上边da 中间的一点进入，连接到 点 。添加边，就得到了 8 v 82 vv 4 v 235 vvv 5 86 ,vv 81 vv 23 35 5267 ,,,vvvv vv vv 8 v 2456372 vvvvvvv 24 vv 84 88387 ,, ,,vvvvvv vv25 vv 1 v e '1 3 K 8 GK 在环面上的一种嵌入，其中e是与 不相关联的一条边。 235 vvv 再考虑图 。我们断言 282 GKK ,3 282,3 2gGgKK ，其中 2,3 K 是一个完全二部图。记 。令 是由 8 18 ,,VK vv234567 ,,,,,vvvvvv 282,3 K 8 GK K 删除边 得到的图。因为 ，所以 14 vv 18 2 ,,vvv4 vvv 28 34 ,,vv, 38 vv 282, GKK 3 8 K 2,38 K gK 28 1gK 2gG 。反证法，假设它有一种在环面上的嵌入 ，即 。考查图 中的三角形 。因为这三个三角形中的每一个 都包含边 ，且都不是可分离的三角形，所以这三个三角形中至少有一个是不可收缩的三角形。我们假定 是不可收缩的三角形。再根据由点 诱导的子图是五个点的完全图，且是与 点不交的子图， 由命题 1.1 知， 诱导的子图只能位于 的一侧，也就是说这个图可以嵌入到平面上，这与 28 gG gK 48 vv 2,3 1K 12 3 67 ,,,,vvvvv 28 GK 123 ,,vvv 2,3 K25846 vvvvv 6 7 ,,vv 458 vvv 8 47 ,,v vvv 8 458 vvv 5 45 vvv 8 K Open Access 188  晁福刚，任 韩 八个点的极小非环面图 不能嵌入到平面上矛盾。这样就证明了 282,3 2gGgKK 8 。 下证 再去掉任意一条边都可以嵌入到环面上。设， 。完全图 282 GKK 141 824 ,,vvvv vvv ,3 2,32 8343 8 ,,,E Kvvvvv 2,31 2 34 8 ,,,,VK vvvvv K 有28 条边，去掉 2,3 K 中的边，还有 22 条边，这些边在同构 的意义下，可以分成三类。以下我们三种情形进行讨论。 情形 3：如果去掉的边是 中的一条，那么得到的图是 12 13 ,,vv vv23 48 ,vv vv8 K 去掉 3 K 及与其关联的一条边得到 的图的一个子图。由情形 1知， 2,3 K e 28 GK 可以嵌入到环面上，其中 e是 中的一条边。 12 vv 13 23 48 ,, ,vvvv vv 情形 4：如果去掉的边是 中的一条边，那么得到的 图是 15 16 ,,vvvv17 ,vv 252627 ,,,vv vv vv35 vv vv 36 37 ,,vv, 56 57 67 ,,vv vv vv 8 K 去掉 2 K 和 的不交并得到的图的一个子图。下面我们给出 4 P8 K 去掉 2 K 和 的不交并得到的图的一个环 面嵌入。先将 4 P 7 K 嵌入到环面上，如图1所示。去掉边 ，将点 放到面 中，添加边 ，再将边，改为由左边 ae 中间的一点出来，由右边 ae 中间的一点进入，由上边 ab 中间的一点出来，再由下边ab 中间的一点进入，连接到点。添加边。经过下边和上边 bc 中间的一点添 加边 ，这样就得到了 23 25 ,,vv vv 5 v 56 1 ,vv vv 78 v 86 vv 24537 vvvvv 82 87 ,,vv vv 84 vv 81 vv 5 8 ,vv 3 8 ,vv 35 vv 2,3 K e 28 GK 在环面上的嵌入，其中 e1 vv是 中的一条边。 5vv 16 17 ,,,vv 25 vv 26 27 ,,vv vv, 3,,vv vv57 ,, 5 36 vv 37 ,vv 56 67 vvvv 情形 5：如果去掉的边是 中的一条边，那么得到的图是 4546 ,,vvvv47 ,vv 58 68 78 ,,vv vv vv8 K 去掉 和的不交并 得到的图的一个子图。先将 3 P3 P 7 K 嵌入到环面上，如图 1所示。去掉边 ，将 点放到面 中，添加边，再将边和边分别按照情形 2和情形 4中的方法改变嵌入的方式，添 加边 和边。这样就得到了 16 67 ,,vv vv23 25 ,vv vv8 v24537 vvvvv 82 84 85 ,,vv vv vv 86 vv 8 ,vv 3 87 ,vv24 vv 35 vv 282,3 GKK e 81 vv 在环面上的嵌入，其中 e是 中 的一条边。 45 vv 46 ,,vv 47 ,vv 58 6 v8 78 ,,v vvvv 最后考虑图 3 P2 K 38 22 KK GK ，其中是一条边，是一条长度为 2的路。我们断言： 。设 3 P 38 gG gK 223 2KKP 78 ,vv 8 12345 ,,,,,vvvvvv6 ,VK 。令 是由 38 223 GK KKP 8 K 删 除边 得到的图。由点 诱导的子图是五个点的完全图，由 Kuratowski 定理知，它 不能嵌入到平面上。又因为 ，所以 12 2345 ,,vvvv vv78 ,vv 38 GK 13456 ,,,,vvvvv 2238 KKP K 8 12 38223 gKK KPggGK 。 反证法，假设它有一种在环面上的嵌入 ，即 38 gG gK2 KKP 23 1 2P 。因为图 有24 条边，由环面上的 Euler 公式 ，得 38 GK K 2 K 3 0ne f 16f ，所以有 23ef ，它是环面上的一个三角剖分图。 考查以 为顶点的三角形，这样的三角形有。因为点 在 中的度数为 7，所以上述的8个三角形中有两个以 为另一个顶点的三角形是可收缩的。 还有 4个三角形 。又因为点 在 2 v 38 2 GK K 246 ,vvv 247 ,vvv 248 ,vvv 258 vvv 2 v 256 ,vvv 257 vv 6 v ,v258 ,vvv 267 ,vvv268 vvv 6 v 23 KP 247 ,vvv 248 ,vvv 257 ,vvv 23 KP 38 GK 2 K2 v 中的度数为 5，以 为顶点 的可收缩的三角形的个数为 5个，且没有可分离的三角形，所以上述的 4个三角形中一定有一个是不可收缩的 三角形。我们假定 是不可收缩的三角形。再根据由点 248 vvv v 1 ,,vv 3, 456 ,vv 诱导的子图是五个点的完全图，且是 与点不交的子图，由命题 1.1知，由点 248 vvv 13456 ,,,,vvvvv诱导的子图只能位于 的一侧，也就是说这个 图可以嵌入到平面上，这与 248 vvv 5 K 不能嵌入到平面上矛盾。这样就证明了 3822 gKK K P 3 2gG 。 下证再去掉 GK 中的任意一条边e，得到的图 38 22 KK 3 P 38 223 GK KKPe 有一个环面 嵌入。设VK ， 2 312 ,,,,K Pvvvv 34578 ,,vvv 12234578 ,,,vv vv vv vv8 22 K K P 23 E。完全图 K 有28 条边， 去掉 223 K KP中的边，还有 24条边，这些边在同构的意义下，可以分成四类。以下分四种情况进行讨论。 情形 6：如果去掉的边是 中的一条边，那么得到的图是 26 27 ,,vv vv28 vv 8 K 去掉 2 K 和 的不交并得到的图的 一个子图，其中是由一个点连接到三个独立的点得到的一个星图。将点 放到面中，设去掉的边为 ，添加边 。将 边按照情形4的方法改变嵌入的方式，连接点 和点 。这样就得到了 1,3 S 23 vv 1,3 S 17 v 8 v5 v 23 24 25 ,,,vv vv vv v 6 v 81 84 ,,vv vvvv85 83 ,,vv 87 82 ,vv vv3 vv 58 v 38 2 K 23 KPe 16 17 ,,vv vv18 34 ,,vv vv35 3 vv vv GK 在环面上的嵌入，其中e是vv 中的一条边。 26 27 ,,vv 2 vv 8 情形 7：如果去掉的边是中的一条边，按照情形 4的方法， 可以将 14 15 ,,vv vv 6 ,, 37 38 ,vv vv 38 22 GK KK 3 P e嵌入到环面上，其中 e是 中的 一条边。 14 vv 1 vv 5 ,, 16 vv vv 17 ,, 18 34 ,,vvvv35 36 ,,vv vv3738 ,vv vv Open Access 189  晁福刚，任 韩 八个点的极小非环面图 Open Access 190 情形 8：如果去掉的边是中的一条边，按照情形5的方法，可以将 4647 ,,vv vv 48 56 ,,vv vv5758 ,,vv vv67 68 ,vv vv 38 223 GK KKPe 嵌入到环面上，其中 e是vv 中的一条边。 4647 ,,vv 48 vv 56 ,,vv5758 ,,vv vv67 68 ,vv vv 情形 9：如果去掉的边是，那么得到的图是 13 vv 8 K 去掉 2 K 和3 K 的不交并得到的图的一个子图。按照情形2 的方法，可以将 38 23 GKKPe 2 K嵌入到环面上，其中e是 中的一条边。 13 vv 综上所述，定理成立。 我们上面的工作实际上是计算了一类图的亏格。Thomassen[8]已经注意到亏格的计算是 NP 问题中的一类， 所以是非常困难的一件事。在这里我们借助于嵌入的技巧。先将它的子图嵌入到一个固定的曲面上，去掉一些 边，并在一个很小的范围内改动原来的嵌入方式，再添加一些点和这个点与其它点之间的边，使得新图也可以 嵌入到这个固定的曲面上。不仅如此，我们的工作还和 Thomassen[9-11]关于临界图的工作有着密切的关系，可以 用来发现小亏格曲面上的点数较少的临界图。 Thomassen[9]找到了环面上的 6-色临界图的确切个数并给出了相关 构造。图 G和图 H的联图 G + H是由图 G添加图 G和图H的所有点之间的边得到的图。如果 和是有 公共点 ，和 中的一条边和中的一条边的图，由这两个图经过 Hajós 构造得到的图是指是具有顶 点集 H1 G2 G 0 v 1 G01 vv 2 G02 vv 1 VG 2 VG 和边集 010 \,v vv 12 v 12 vv 2 EG EG的图。Thomassen[9]证明了：环面上的嵌入图是 5- 色的，除非它包含或者 6 K ，六个点的完全图，或者 35 CC ，长度为 3和5的两个圈的联图，或者 27 K H 、2 K 和7 H 的联图，其中7 H 是由在 4 K 的两个拷贝上应用Hajós 构造得到的，或者环面上有 11个点的三角剖分图 ， 它是由长度为11 的圈添加圈上的距离为 2和3点之间的边得到的图。一个有趣的问题是：其它的曲面上的临界 图是否有类似的结果？Chenette、Postle、Streib、Thomas 和Yerger[12]、Kawarayabashi、Král、Kynčl和Lidický[13] 使用不同的方法得到了克莱因瓶上的6-色临界图完全列表。 11 T 参考文献 (References) [1] Thomassen, C. (1992) The Jordan-Schönflies theorem and the classification of surfaces. Ameri c a n Ma t h e m a t i c al Monthly, 99, 116-130. [2] Mohar, B. and Thomassen, C. (2001) Graphs on surfaces. Johns Hopkins University Press, London. [3] Kuratowski, C. (1930) Sur le probléme des courbes gauches en topologie. Fundamenta Mathematicae, 15, 271-283. [4] Heawood, P.J. (1890) Map colour theorem. The Quarterly Journal of Pure and Appl i e d Mathematics, 24, 332-338. [5] Ringel, G. and Youngs, J.W.T. (1968) Solution of the Heawood map-coloring problem. Proceedings of the National Academy of Sciences of the United States of America, 60, 438-455. [6] Franklin, P. (1934) A six color problem. Journal of Mathematical Physics, 13, 363-369. [7] Rringel, G. (1974) Map color theorem. Springer, Berlin. [8] Thomassen, C. (1989) The graph genus problem is NP-complete. Journal of Algorithm s, 10, 568-576. [9] Thomassen, C. (1993) Five-coloring maps on surfaces. Journal of Combinatorial T h e o r y, Series B, 59, 89-105. [10] Thomassen, C. (1997) Color-critical graphs on a fixed surface. Journal of Combinato r ial Theory, Series B, 70, 67-100. [11] Thomassen, C. (2003) The chromatic number of a graph of girth 5 on a fixed surface. Journal o f C o m b i n a t o r ial Theory, Series B, 87, 38-71. [12] Chenette, N., Postle, L., Streib, N. and Thomas, R. (2012) Five-colorings graphs on the Klein bottle. Journal of Combinatorial Theory, Series B, 102, 1067-1098. [13] Kawarayabashi, K.I., Král, D., Kynčl, J. and Lidický, B. (2009) 6-critical graphs on the Klein bottle. SIAM Journal on Discrete Mathematics, 23, 372-383. |