完全图

完全图把成对连接推到简单图允许的上限。两点之间无需经过中间顶点，距离恒为一；与此同时，任何要求相邻顶点彼此区别的约束也会最紧，因为没有两点能够共享“互不冲突”的位置。

它还是固定顶点数图的通用宿主。研究任意 $n$ 顶点图时，可以先从 $K_n$ 出发，再说明删去了哪些边；研究局部的全连接结构时，则在母图中寻找由某组顶点诱导出的 $K_k$。全图与局部模式由此使用同一个标准对象。

一个需要任意两台设备都以专线直接通信的网络，其无向骨架是完全图。设备从 $n$ 增到 $n+1$ 时，新设备必须增加 $n$ 条链路，总代价按 $(\genfrac{}{}{0ex}{}{n}{2})$ 二次增长；这个具体增量解释了全互联架构为何很快变得昂贵。

$K_3$ 是三角形。$K_4$ 虽然把四点画在凸四边形上时两条对角线会交叉，却可以把一个顶点移入三角形内部而得到无交叉嵌入；$K_5$ 不可平面。因为 $K_n$ 在 $n\ge 5$ 时含 $K_5$ 子图，所有更大的完全图也不可平面。

完全二分图 $K_{m,n}$ 只包含跨越两侧的边，同侧顶点不相邻。当 $m,n>0$ 时，它只有在 $m=n=1$ 的情况下也是完全图。术语中的“完全”分别表示“所有顶点对”与“所有跨侧顶点对”，量词范围不能省略。

$K_0$ 与 $K_1$ 都没有边，公式仍成立；$K_1$ 通常视为连通，$K_0$ 的连通性依约定。完全图的定义属于简单无向语境。有向完全图可能指每对顶点之间恰选一个方向的 tournament，也可能指两个方向都出现的对称有向图，必须另行说明。

图 $G$ 的顶点集 $C$ 是团公理库团与独立集Clique · Independent set · 团 · 独立集顶点集内部的边关系分别达到两两全有与两两全无时形成的两类结构。，当且仅当诱导子图 $G[C]$ 是完全图。于是团数 $\omega (G)$ 正是嵌入 $G$ 的最大完全子图阶数。对无自环简单图，图同态 $K_k\to G$ 必为单射，也因此恰好给出一个带标号的 $k$-团。

在任意正常顶点着色中，$K_n$ 的顶点两两冲突，必须使用 $n$ 种颜色；所以其色数公理库色数Chromatic number一张图存在正常顶点染色所需的最少颜色数。为 $n$。更一般地，$G$ 中每个 $K_k$ 都给出下界 $\chi (G)\ge k$。

完全图含有所有可能的生成树。Cayley 公式公理库Cayley 树计数公式Cayley's formula顶点集固定为 $[n]$ 的标号树恰有 $n^{n-2}$ 棵。给出 $K_n$ 的标号生成树数 $n^{n-2}$（$n\ge 2$）；这等价于计数顶点集 $[n]$ 上的全部标号树，而非只计某一种树形。

Ramsey 理论公理库Ramsey 定理Finite Ramsey theorem足够大的有限结构中必然出现给定大小的同质子结构。把 $K_n$ 当作所有成对关系均已出现的宿主，再给边或顶点着色，研究规模足够大时必然出现的单色规则子图。平面图公理库平面图Planar graph · Plane graph可把顶点与边嵌入平面且除公共端点外没有交叉的抽象图。理论则从相反方向说明：全连接增长到五个顶点时，平面已容纳不了全部边。