完全图

完全图是一个图，其中每对图顶点都由一条边连接。具有 个图顶点的完全图表示为 ，并具有 （三角形数）条无向边，其中 是一个二项式系数。在较早的文献中，完全图有时被称为通用图。

完全图 也是完全 n-部图 。

在 个节点上的完全图在 Wolfram 语言中实现为CompleteGraph[n]。预计算的属性可以使用GraphData["Complete", n]。可以使用 Wolfram 语言中的函数来测试图是否完整CompleteGraphQ[g]。

0 个节点的完全图是一个被称为零图的平凡图，而 1 个节点的完全图是一个被称为单点图的平凡图。

在 1890 年代，Walecki 证明了对于奇数 ，完全图 允许哈密顿分解，对于偶数 ，允许分解为哈密顿环加上完美匹配（Lucas 1892，Bryant 2007，Alspach 2008）。Alspach et al. (1990) 给出了所有 的哈密顿分解的构造。

完全图 的图补是 个顶点上的空图。 的单纯形图是超立方体图 （Alikhani 和 Ghanbari 2024）。

的图亏格为 ，对于 (Ringel 和 Youngs 1968；Harary 1994，p. 118)，其中 是天花板函数。

完全图 的邻接矩阵 采用特别简单的形式，即全为 1，对角线上为 0，即单位矩阵减去单位矩阵，

(1)

完全图是距离正则、几何和支配唯一的。

是环图 ，以及奇图 （Skiena 1990，p. 162）。 是四面体图，以及轮图 ，也是一个平面图。 是非平面的，有时被称为五胞体图或 Kuratowski 图。Conway 和 Gordon (1983) 证明了 的每个嵌入都是本征链接的，至少有一对链接的三角形，并且 也是一个凯莱图。Conway 和 Gordon (1983) 还表明， 的任何嵌入都包含一个打结的哈密顿环。

对于 、2、3 和 4，完全图 是平面图。对于 、6 和 7，它是非平面图，其图交叉数等于其直线交叉数。盖伊猜想提出了 的图交叉数的闭合形式，这首先与 的直线交叉数不同，其中 但 。上面说明了最小交叉嵌入，其中显示了 的最小直线和无限制（允许曲线边）最小嵌入（Harary 和 Hill 1962-1963）。

完全图 是线图，星图 的线图。

的色多项式 由降阶乘 给出。 独立多项式由下式给出

(2)

和匹配多项式由下式给出

			(3)
			(4)

其中 是埃尔米特多项式 的归一化版本。

的色数和团数是 。完全图 的自同构群是对称群 （Holton 和 Sheehan 1993，p. 27）。

对于 、4、...，完全图 中的图环数为 1、7、37、197、1172、8018 ... (OEIS A002807)。这些数字由以下公式解析给出

			(5)
			(6)

其中 是二项式系数， 是广义超几何函数 (Char 1968, Holroyd 和 Wingate 1985)。

完全图是测地线的。

一般而言，是否可以将一组具有 1、2、...、 条图边的树总是打包到 中尚不清楚。但是，如果将树的选择限制为每个族中的路径或星形，则始终可以完成打包（Zaks 和 Liu 1977，Honsberger 1985）。

完全图 的二分双图是皇冠图 。