八个点的极小非环面图

Minimal Nontoroidal Graphs on Eight Vertices

借助于嵌入的技巧,证明了由K8,八个点的完全图,去掉K3,三角形,或K2,3,部集的点数为2和3的完全二部图,或K2∪K2∪P3,长度为1的两条路和长度为2的一条路的不交并,中的边得到的图是极小的非环面图。

Using the technique of embedding, we prove that the graphs obtained fromK8 , the complete graph on eight vertices, by deleting the edges ofK3 , a triangle, orK2,3 , the complete bipartite graph with 2 vertices and 3 vertices, orK2∪K2∪P3 , the disjoint union of two paths of length one and one path of length two, are minimal nontoroidal graphs.