完全图

完全图把成对连接推到简单图允许的上限。任意两个不同顶点之间都有一条直接边，因此距离为一；顶点到自身的距离仍为零。对于正常着色，每个顶点都与其余顶点冲突，给一个顶点使用的颜色便不能再给任何别的顶点使用，所以需要 $n$ 种颜色。

它还是固定顶点数图的通用宿主。研究任意 $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$ 的色数理路色数Chromatic number一张图存在正常顶点染色所需的最少颜色数。 $\chi (K_n)=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可把顶点与边嵌入平面且除公共端点外没有交叉的抽象图。理论则从相反方向说明：全连接增长到五个顶点时，平面已容纳不了全部边。