形式陈述

完全图 $K_n$$K_n$ 是含 $n$$n$ 个顶点且任意两个不同顶点之间恰有一条边的简单无向图。其边数为 $\binom n2$$(\genfrac{}{}{0ex}{}{n}{2})$，每个顶点度为 $n-1$$n-1$，染色数和团数均为 $n$$n$。补图为空图。完全图定义依简单无向语境；有向完全图和多重图需另行命名。

直觉

所有顶点彼此相邻，没有任何缺失的可能连接，因此它是给定顶点数上最稠密的简单图。

例子与边界

$K_3$$K_3$ 是三角形，$K_4$$K_4$ 可平面嵌入，而 $K_5$$K_5$ 非平面。对 $n\ge2$$n\ge 2$，Cayley 公式给出 $K_n$$K_n$ 的生成树数为 $n^{n-2}$$n^{n-2}$；$K_1$$K_1$ 则按定义只有一棵生成树。完全二分图 $K_{m,n}$$K_{m,n}$ 只连接两侧顶点，通常不是完全图。

推论与应用

完全图是团、Ramsey 理论、平面性禁图和最坏情形稠密网络的基准对象。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，Chs. 1–5。
• Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，Parts I–V。