图是顶点和边的集合。如果图中的每个顶点之间都有一条边相连，则此图被称为“完全图”。如果在这个完全图中，移除相对于总边数较少的边，就生成了一个“近完全图”。

数学定义

假定一个具有个v顶点、e条边和亏格g的图。

计算X=(e-3v+6)/6

令⎡X⎤表示大于或等于X的最小整数。所有图都满足欧拉下界

g≥⎡X⎤

完全图有g=⎡X⎤，边界是饱和的。

可以从一个完整的图开始，删除p条边，使得剩余的图满足

• 欧拉的下界是饱和的g=⎡X⎤
• 图是连通的

令NC(n)表示从完全图Kn中可能移除的边的最大数量，使得无论哪些边被移除，上述两个属性都成立。有n条边的图，如果它可以通过从完全图Kn中移除p≤NC(n)条边而得到，那么我们就可以称它为近完全图。

参考文献

• The genus of nearly complete graphs-case 6, Jonathan L. Gross, Aeq. Math. 13, 243–249 (1975) doi:10.1007/BF01836527