1、对于任何v≥3的图都有3f≤2e的关系，把把f≤2e/3代入多阶曲面上图的欧拉公式v＋f－e＝2（1－n）（n是图的亏格）得e≤3v－6（1－n）（v≥3）这就是多阶曲面上图中顶点与边的关系。再把完全图边与顶点的关系e＝v（v－1）/2代入该式中得v（v－1）/2＝3v－6（1－n），整理后得一元二次不等式v2－7v＋12（1－n）≤0，解这个一元二次不等式，得其正根是v≤（7＋√（1＋48n））/2，这就是不同亏格的图中完全图的顶点数，也是图的最小完全同态的顶点数。由于图的色数就等于图的最小完全同态的顶点数，所以这也就是赫渥特的多阶曲面上的地图着色公式。
2、每一个亏格的曲面上都对应有一个最大的完全图KV，其顶点数v也就是该图的色数。如果在该最大完全图（即图中的最大团）外有一条不可同化道路时，这条道路中一定有一个顶点同化不到最大团中去，该图的色数就一定是v＋1，该图的最小完全同态就是KV＋1。那么这个有一条不机同化道路的最大完全图的亏格还是不是这个最大完全图的亏格呢？请看下面的证明：
3、在亏格为n的曲面上的最大完全图KV外有一条由S个顶点构成的不可同化道路PS的图的总边数是由①该完全图的边数v（v－1）/2与②有S个顶点的不可同化道路的边数S－1以及③道路中各顶点与最大团相邻的边S（v－2）＋2（道路中每个顶点都与最大团中的v－2个顶点相邻，两个端点顶点又各再与最大团中v－2个顶点以外的两个顶点中的一个顶点相邻）三部分合成，即该图的总边数等于v（v－1）/2＋S－1＋S（v－2）＋2，再把亏格为n的最大完全图的顶点数v＝（7＋√（1＋48n））/2代入其中，化简并整理后得到e1＝｛44＋（12＋4S）•√（1＋48n）＋48n＋20S｝/8，当n＝0时有e＝7＋3S；当n＝1时有e＝22＋6S；当n＝2时有e＝31＋7S等等。
4、亏格为n的曲面上的图的最大边数是e＝3v－6（1－n）（v≥3），同样的把亏格为n的最大完全图的顶点数v＝（7＋√（1＋48n））/2与PS道路的顶点数S代入其中，化简并整理后得到e2＝｛36＋12•√（1＋48n）＋48n＋24S｝/8，当n＝0时有e＝6＋3S；当n＝1时有e＝21＋3S；当n＝2时有e＝30＋3S等等。
5、用e1＝｛44＋（12＋4S）•√（1＋48n）＋48n＋20S｝/8减e2＝｛36＋12•√（1＋48n）＋48n＋24S｝/8得e1－e2＝｛8＋4S［√（1＋48n）－1］｝/8＝1＋S［√（1＋48n）－1］/2。当n＝0时有e1－e2＝1；当n＝1时有e1－e2＝1＋3S；当n＝2时有e1－e2＝1＋4S等。由于n≥0和S≥2（S＝1时，图中的最大团就是KV＋1，而不再是KV了，图的亏格也可能不是n而是n＋1了），所以e1－e2总是大于1的，说明e1总是大于e2的。由于e2是亏格为n的曲面上图的最大边数，e1≥e2就说明了那个有一条不可同化道路的完全图KV＋PS是不能嵌入到亏格为n的曲面上的，而只能入亏格为n＋1的曲面上。这就说明了任何曲面上的图的最小完全同态的顶点数是不会大于该曲面上的最大完全图的顶点数的，也说明了该曲面上的图的色数是不会大于该曲面上最大完全图的顶点数的，更说明了该曲面上的图的最小完全同态的亏格是不会大于其原图的亏格的。
6、举例：
在亏格n＝0，最大完全图K4外有一条顶点数是3的不可同化道路时，其总边数是：e1＝4×3/2＋3×（4－2）＋3－1＋2＝16，该曲面上可嵌入的图的最大边数是：e2＝3×（4＋3）＋6×（0－1）＝15，二者之差是1；e1－e2＝1。
① 当亏格n＝1，最大完全图K7外也有一条同样的不可同化道路时，其总边数是：e1＝7×6/2＋3×（7－2）＋3－1＋2＝40，该曲面上可嵌入的图的最大边数是：e2＝3×（7＋3）＋6×（1－1）＝30，二者之差是10；e1－e2＝10。
② 当亏格n＝2，最大完全图K8外也有一条同样的不可同化道路时，其总边数是：e1＝8×7/2＋3×（8－2）＋3－1＋2＝50，该曲面上可嵌入的图的最大边数是：e2＝3×（8＋3）＋6×（2－1）＝39，二者之差是11；10；e1－e2＝11。
③ 当亏格n＝3，最大完全图K9外也有一条同样的不可同化道路时，其总边数是：e1＝8×7/2＋3×（9－2）＋3－1＋2＝61，该曲面上可嵌入的图的最大边数是：e2＝3×（9＋3）＋6×（2－1）＝48，二者之差是12；e1－e2＝13。
等等等等。
7、看来无论曲面的亏格是多大，不可同化道路上有多少个顶点，e1－e2总是大于等于0的，这就证明了任何图的最小完全同态的亏格是不会大于其原图的亏格的。
IP卡
狗仔卡
发表于 2016-4-16 17:56
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
楼主