完全图

完全图是任意两个不同顶点都由一条边直接相连的简单无向图。它表示网络中每一对对象之间都有关系，而不是仅要求任意两个顶点之间能经过若干条边到达。

定义和小例子

具有 $n$ 个顶点的完全图记为 $K_{n}$ 。例如 $K_{4}$ 的四个顶点中，每个顶点与另外三个顶点相邻。把四个点画在平面上时，边可以发生交叉；交叉位置如果没有被指定为顶点，就不构成额外的顶点。

四个顶点位于正方形四角，四条边和两条对角线全部画出，对角线交叉处不是顶点 — K4 的四个顶点两两相邻，共有六条边。两条对角线的交叉不增加顶点。

计数

每条边对应一个无序的不同顶点对，因此 $| E (K_{n}) | = (\binom{n}{2}) = \frac{n (n - 1)}{2} .$ 每个顶点的度为 $\deg (v) = n - 1$ 。例如 $K_{4}$ 有 $4 \times 3 / 2 = 6$ 条边。也可以先计算各顶点的度数和 $4 \times 3 = 12$ ，再用握手引理除以 2。^[1]

选择任意 $k$ 个顶点，它们之间仍两两相邻，所以构成一个 $K_{k}$ 。因此 $K_{n}$ 中由顶点集合决定的 $K_{k}$ 子图有 $(\binom{n}{k})$ 个。例如 $K_{5}$ 中三角形数量是 $(\binom{5}{3}) = 10$ 。这里不把同一个三角形按顶点的排列重复计数。

着色与邻接矩阵

在顶点着色中，相邻顶点必须使用不同颜色。 $K_{n}$ 的每一对顶点都相邻，所以至少需要 $n$ 种颜色；给每个顶点一种颜色又足以完成着色。因此其色数为 $χ (K_{n}) = n$ 。

若顶点编号为 $1, \dots, n$ ，邻接矩阵的对角线为零，其他位置均为一，即 $A = J_{n} - I_{n} .$ 其中 $J_{n}$ 为全一矩阵。全一向量是特征值 $n - 1$ 的特征向量；对分量之和为零的向量 $x$ ，有 $J_{n} x = 0$ ，故 $A x = - x$ 。当 $n \geq 2$ 时，矩阵的特征值是一个 $n - 1$ 和 $n - 1$ 个 $- 1$ 。

完全与连通

$K_{n}$ 在 $n \geq 1$ 时连通，但连通图不一定完全。例如四顶点路径中首尾两点可以沿路径到达，二者却没有直接边。完全图在描述两两直接联系时有用；当网络规模大而边很少时，用它表示会把不存在的联系也算进去。

参考资料

↑ James Aspnes，Notes on Discrete Mathematics，第 10 章，完全图与简单图。

[1] James Aspnes，Notes on Discrete Mathematics，第 10 章，完全图与简单图。

[1]