图的最小完全同态的亏格一定小于等于原图亏格的证明

雷明85639720

图的最小完全同态的亏格一定小于等于原图亏格的证明
雷  明
（二○一五年元月四日）

前几天写了一篇《关于图的亏格——兼论四色猜测的证明》的文章，自我感到其中对图的最小完全同态的亏格一定小于等于原图的亏格的证明还不太专业，有必要在这里再进行专门论述这一问题。
图的最小完全同态是通过对原图的同化而得到的，只要严格按照同化的两不相邻顶点间的距离最短（即两顶点间只间隔一个别的顶点）的原则进行操作，最后一定得到的是原图的最小完全同态。
图的最小完全同态就是一个完全图，是图都有其亏格，那么图的最小完全同态的亏格与其原图的亏格之间是什么关系呢。
上面说了，图的最小完全同态是通过同化运算得来的，且同化运算是图的顶点数与边数在不断减少的过程。可以说同化过程中，图本身也是处在一个由复杂图到简单图的变化过程中。这一变化表现在最小完全同态的顶点和边数都是比原图减少了的，有时图的亏格也是减小的，而只有当图是完全图时，本身就不需要同化，所以其最小完全同态的顶点数、边数以及亏格才不会发生变化的。比如，K3,3图有6个顶点，9条边，其最小完全同态是K2，只有2个顶点和一条边，其亏格由原来的1变成了0；有多个悬挂顶点的K5图的最小完全同态就是一个K5图,顶点数与边数都减少了，但亏格仍是1；只有K5图的最小完全同态仍是K5图，顶点数、边数和亏格都没有发生变化。
最小完全同态的顶点数与边数都比原图少了，那么其亏格会不会大于原图的亏格呢。我们不仿假设最小完全同态的亏格大于原图的亏格，采用反证明法进行证明。既然最小完全同态的亏格大于原图的亏格，那么它一定是不能嵌入到与原图同亏格的曲面上的。这一点是不可含乎的。但这一假设也是不可能成立的。因为同化过程本身就是在与原图同亏格的曲面上进行的，最小完全同态仍是在原亏格曲面上的，最小完全同态中也没有出现交叉边，应该说该最小完全同态也是嵌入在该亏格曲面上的图。
比如，我们用橡皮筋结一个亏格为n的图，同时也把该图嵌入一个与其亏格相同的曲面上，按照正确的同化方法进行同化，只要一出现平行边就把其中一条剪掉，只留一条，直到最后图中既无不相邻顶点，又无平行边时，这个所剩的完全图就是原图的最小完全同态。但是，原图所嵌入的曲面的亏格，是否就是该最小完全同态的亏格，还仍然不能确定。因为图的亏格是其所能嵌入的所有曲面的最小亏格，而原图所嵌入曲面的亏格不一定就是该最小完全同态所能嵌入的曲面的最小亏格。比如，K3,3图的最小完全同态K2图虽然仍嵌入在亏格是1 的环面上，但1并不是K2图的亏格，K2图的亏格应是0，也就是说K3,3图的最小完全同态的亏格应是0。但至少可以肯定，该最小完全同态的亏格一定是不会大于原图所能嵌入的曲面的亏格的，即最小完全同态的亏格一定是小于等于原图的亏格的。这与原假设的“最小完全同态的亏格大于原图的亏格”便设产生了矛盾，应否定假设。所以就有图的最小完全同态的亏格一定是小于等于原图的亏格的。

雷  明
二○一五年元月四日于长安

注：此文已于二○一五年元月四日发表在《中国博士网》上。