正则图

正则图是每个顶点的度都相同的图。若共同的度为 $k$，称为 $k$ 正则图。这里讨论有限简单无向图，因此每条边连接两个不同顶点，且同一顶点对之间至多一条边。

从环和完全图认识正则

环图 $C_5$ 的五个顶点排成一圈，每个顶点恰好连接两侧邻居，所以是 2 正则图。完全图 $K_5$ 中，每个顶点连接另外四个顶点，因而是 4 正则图。没有边的图是 0 正则图；顶点度相同并不要求整个图连通。

五顶点环 C5：每个顶点的度均为二。

例如两个互不相连的三角形，每个顶点仍有两条相邻边，因此是一个不连通的 2 正则图。反之，连通也不保证正则：一条四顶点路径的两个端点度为一，中间顶点度为二。

边数和必要条件

设 $G$ 是有 $n$ 个顶点、$m$ 条边的 $k$ 正则图。将各顶点的度相加，再用每条边计数两次，得到 $$nk=\sum _{v\in V}\mathrm{deg}(v)=2m,m=\frac{nk}{2}.$$ 例如 $C_5$ 的边数是 $5\times 2/2=5$。这也给出一个必要条件：$nk$ 必须是偶数。若有人提出有五个顶点的 3 正则简单图，它的边数应为 $15/2$，不是整数，因此不存在。

简单图中一个顶点最多与其余 $n-1$ 个顶点相邻，故 $0\le k\le n-1$。这两个条件描述了有限简单图的基本限制；遇到其他类型的图时，能否有环和多重边会改变度数的解释。

补图与矩阵

$G$ 的补图保留原顶点，并将原来不相邻的不同顶点连边。原图中每个顶点有 $k$ 个邻居，另外 $n-1-k$ 个不同顶点恰好是它在补图中的邻居，因此补图是 $(n-1-k)$ 正则图。$C_5$ 的补图也是 2 正则图，实际上同构于另一个五顶点环。

对邻接矩阵 $A$ 和全一向量 $\mathrm{𝟏}$，每行之和为 $k$，故 $$A\mathrm{𝟏}=k\mathrm{𝟏}.$$ 这说明 $k$ 是邻接矩阵的一个特征值，但不能单靠这个特征值断定图连通。例如两个互不相连的三角形也有特征值 2。