1 基本定义
1.1 完全图的定义
完全图是指任意两个不同顶点之间都恰好由一条边相连的简单图。换言之，在这样的图中，顶点之间不存在“缺边”的情况，每一对顶点都彼此可达并直接相连。由于连接关系最为密集，完全图常被视为图论中最典型的“全连接”模型。
1.2 记号与表示方法
1.2.1 K_n 的含义
完全图通常记作 \(K_n\)，其中 \(n\) 表示顶点数。这个记号强调图的规模完全由顶点个数决定，而边的数量则由完全连接的规则自动确定。对于给定的 \(n\)，\(K_n\) 在同构意义下是唯一的。
1.2.2 图示与抽象表示
在图示中，完全图往往画成若干顶点围成一圈，并以直线或曲线将每一对顶点连接起来。随着顶点数增加，图形会迅速变得复杂，但其本质仍是“任意两点相连”。在抽象研究中，通常只关注其顶点集与边集，而不依赖具体画法。
1.3 简单图与完全图的关系
1.3.1 无自环与无重边要求
完全图建立在简单图的定义之上，因此不允许自环，也不允许两顶点之间出现多重边。每条边都对应一对不同顶点，且这对顶点之间至多只有一条边。
1.3.2 完全图作为简单图特例
在简单图家族中，完全图可以看作极端稠密的特例。与一般简单图相比，它将“允许的边”全部取满，因此常用于检验和比较各种图性质，尤其适合作为极值情形的参照对象。
2 基本性质
2.1 顶点与边的数量
2.1.1 边数公式
若完全图为 \(K_n\)，则其边数为 \(\frac{n(n-1)}{2}\)。这是因为每一对不同顶点都对应一条边，而顶点对的总数正是从 \(n\) 个顶点中任选 2 个的组合数。
2.1.2 顶点度数分布
在 \(K_n\) 中，每个顶点都与其余 \(n-1\) 个顶点相连，因此所有顶点的度数完全相同，均为 \(n-1\)。这意味着完全图的度数分布极为均匀，没有任何“孤立”或“边缘”顶点。
2.1.3 邻接关系特征
完全图中任意两个不同顶点都是相邻的，因此其邻接矩阵在对角线外的元素全部为 1，对角线元素为 0。这样的结构反映出它的连接关系最为紧密，也使许多图算法在完全图上的表现具有明显的边界特征。
2.2 对称性与正则性
2.2.1 顶点传递性
完全图具有高度对称性，任意一个顶点都可通过图的自同构映射到另一个顶点，因此从结构上看，各顶点地位完全相同。这种顶点传递性使得完全图在研究对称图时经常被当作基础样本。
2.2.2 边传递性
不仅顶点之间对称，完全图中的任意一条边也处于同样的结构位置。任何边都可以通过图的对称变换映射到另一条边，因此它也是边传递的。这样的性质说明完全图没有局部特殊结构。
2.2.3 正则图性质
完全图是典型的正则图，并且属于 \((n-1)\)-正则图，即每个顶点的度数都相同且等于 \(n-1\)。正则性与高对称性共同构成了完全图的重要特征，使其在理论分析中尤为方便。
2.3 连通性
2.3.1 连通图的最强形式
完全图当然是连通图，而且连通性达到一种极强的形式：任意两点之间都存在直接边连接，不需要经过中间顶点即可到达。因而它的直径为 1（当 \(n \ge 2\) 时）。
2.3.2 割点与割边性质
当顶点数足够大时，完全图不含割点，也不含割边。删除任意一个顶点或任意一条边，图通常仍保持连通。这说明完全图具有很强的结构冗余性，不容易因局部删除而分裂。
3 特殊情形
3.1 小阶完全图
3.1.1 K_1
\(K_1\) 只有一个顶点，没有边。它常被视为完全图族中的最小成员。虽然结构极为简单，但在递推和边界讨论中仍然具有意义。
3.1.2 K_2
\(K_2\) 由两个顶点和一条边组成，是最简单的非平凡完全图。它体现了“任意两点相连”的基本要求，也常作为路径、匹配等概念的最小例子。
3.1.3 K_3
\(K_3\) 是一个三角形图，三个顶点两两相连。它是最常见的完全图示例之一，同时也是团、染色和平面图讨论中的基本对象。
3.2 边界情况与退化情形
3.2.1 空图与完全图的区别
空图通常指没有边的图，而完全图恰好是边尽可能多的图，二者在结构上形成鲜明对比。前者强调完全分离，后者强调完全连接，因此常被一起用于说明图论中的极端情形。
3.2.2 单顶点图的理解
单顶点图可看作 \(K_1\)，它既没有可连接的另一顶点，也没有边可添加。虽然在直观上似乎“什么都没有”，但在形式定义下它仍属于完全图，并可作为许多归纳证明的起点。
3.3 完全图族的递推关系
3.3.1 从 K_n 到 K_{n+1} 的扩展
从 \(K_n\) 构造 \(K_{n+1}\) 的方式很直接：加入一个新顶点，并将其与原图中的每个顶点分别相连。这样就得到一个更大阶的完全图。这种扩展方式体现了完全图族的递推性。
3.3.2 子图与诱导子图关系
完全图的任意顶点子集所诱导出的子图仍是完全图。也就是说，\(K_n\) 的任意 \(m\) 个顶点构成的诱导子图同构于 \(K_m\)。这一性质使完全图在子图分析中具有非常清晰的层级结构。
4 重要定理与公式
4.1 边数公式证明
4.1.1 组合计数法
完全图的边数可通过组合数直接得到。因为边对应的是无序顶点对，而从 \(n\) 个顶点中选出 2 个顶点的方式共有 \(\binom{n}{2}\) 种，所以边数为 \(\binom{n}{2}=\frac{n(n-1)}{2}\)。
4.1.2 递推证明法
也可以用递推方式证明边数公式。已知 \(K_n\) 有 \(\frac{n(n-1)}{2}\) 条边，构造 \(K_{n+1}\) 时，新加入的顶点要与原来的 \(n\) 个顶点分别连边，因此新增 \(n\) 条边，总数变为 \(\frac{n(n-1)}{2}+n=\frac{n(n+1)}{2}\)，与公式一致。
4.2 度数和公式
4.2.1 握手定理应用
根据握手定理，图中所有顶点度数之和等于边数的 2 倍。对 \(K_n\) 而言，每个顶点度数都是 \(n-1\)，共有 \(n\) 个顶点，因此度数和为 \(n(n-1)\)。这也与边数公式完全吻合。
4.2.2 平均度计算
完全图的平均度等于每个顶点的度数，也就是 \(n-1\)。由于所有顶点度数一致，平均度不需要复杂统计即可直接得出。该性质体现了完全图在局部结构上的均匀性。
4.3 团与完全图的关系
4.3.1 最大团的定义
团是指图中两两相邻的一组顶点。若一个团的顶点数尽可能大，则称为最大团。最大团问题是图论与算法中的经典问题之一，常用于衡量图中“完全连接”结构的规模。
4.3.2 完全图作为团的典型实例
完全图本身就是一个团，而且是顶点数为 \(n\) 的最大团。它提供了团概念最直接的模型，因此常被拿来说明团、极大团和最大团之间的区别。
5 图论中的相关概念
5.1 完全子图
5.1.1 团的概念
完全子图指的是原图中一个顶点集合所诱导出的完全图，通常也称为团。它反映了原图内部某一部分的完全连接程度，是分析图结构的重要工具。
5.1.2 最大团与极大团
极大团是指不能再通过添加顶点而保持为团的团，而最大团则是在所有团中顶点数最多的团。两者不一定相同：极大团强调“无法继续扩展”，最大团强调“规模最优”。
5.2 完全二部图的对比
5.2.1 结构差异
完全图与完全二部图虽然名称相近，但结构差异明显。完全图要求同一集合内任意两点相连，而完全二部图则要求顶点分成两部分，边只出现在不同部分之间，部分内部不连边。
5.2.2 性质差异
完全图具有高密度、单一连通块和高度对称的特征；完全二部图则体现出分层连接的结构，常用于匹配与二分关系建模。前者的所有顶点等价，后者则天然带有两类顶点的区分。
5.3 补图关系
5.3.1 完全图的补图性质
完全图的补图是空图，因为在完全图中已经存在所有可能的边，补图中便没有边可补。这个对应关系非常简洁，是图与补图互补结构的典型例子。
5.3.2 与独立集的对应关系
在补图中，完全图对应的空图具有最大独立集结构：任意顶点之间都不相邻。因而，完全图中的团与补图中的独立集之间存在直接对应关系，这也是图论中常见的对偶思路。
6 典型应用
6.1 染色问题
6.1.1 色数与完全图
完全图的色数等于其顶点数，因为任意两个顶点都相邻，必须为每个顶点使用不同颜色。这一结论使完全图成为研究图染色时最基本的下界参考。
6.1.2 最坏情况参考模型
在算法分析中，完全图常被视为染色问题的“最坏情况”之一。由于边最多，颜色冲突也最密集，因此许多启发式方法在完全图上会暴露出最明显的资源需求。
6.2 网络模型
6.2.1 全连接网络抽象
完全图常用来抽象全连接网络，即任意两个节点之间都可以直接通信的系统。虽然现实网络很少真正达到这种程度，但它是评估冗余性和连接效率的理想化模型。
6.2.2 通信路径与冗余分析
在完全图中，任意两点间都存在最短的直接路径，因此通信延迟在模型上最小。同时，由于连接非常丰富，单条边的失效通常不会影响整体连通性，体现出较强的冗余能力。
6.3 组合数学
6.3.1 计数模型中的使用
完全图经常被用作计数问题中的基础构造，例如统计顶点对、边集合或子图数量。由于结构规则明确，许多组合推导可以在完全图上先获得清晰结果，再推广到更一般情形。
6.3.2 作为构造与反例工具
完全图还常被用作构造例子或反例。某些性质在完全图上表现得最极端，因此它既能验证命题的边界，也能帮助说明一般图中可能出现的极端现象。
7 相关扩展
7.1 加权完全图
7.1.1 边权设置
在加权完全图中，每一条边都被赋予一个权值，权值可以表示距离、代价、容量或相似度等信息。此时图仍保持完全连接，但研究重点从“是否相连”转向“连接的代价如何”。
7.1.2 最短路与最小生成树背景
加权完全图常出现在最短路、旅行商问题和最小生成树等背景中。由于边数极多，这类图既为算法提供了完整输入，也使一些优化问题呈现出更强的计算挑战。
7.2 有向完全图
7.2.1 完全有向图的定义
完全有向图是指任意两个不同顶点之间都存在一对相反方向的弧，或者在某些约定下，每对顶点之间至少有一个方向的连接。不同文献对其具体定义可能略有差异，但核心都是“方向上的完全连接”。
7.2.2 与无向完全图的区别
无向完全图只关注顶点对之间是否相连，而有向完全图还要考虑方向信息，因此结构更细致。后者在表示流程、优先级和单向关系时更有表现力，但对称性通常不如无向情形简单。
7.3 无限完全图
7.3.1 理论上的推广
在理论图论中，可以把完全图的概念推广到无限顶点集合上，即任意两个不同顶点之间都相连的无限完全图。这一推广主要用于纯理论讨论，帮助研究无限图的结构性质。
7.3.2 适用范围与限制
无限完全图更多见于抽象数学研究，而不是常规应用场景。由于顶点无限，其许多有限图中的计数公式不再直接适用，因此研究重点往往转向连通性、子图结构和集合论层面的性质。