前置知识：图论基础 – 第1集, 第2集
正则图：
如果一个图中每个顶点的度数都相等，我们称之为正则图。如果图中每个顶点的度数都是 K，我们称之为 K 正则图。
示例：
让我们观察下图：
这个图中每个顶点的度数都是 2。因此，它是 2 正则图。同理，下面的两个图分别是 3 正则图 和 4 正则图。
正则图的性质：
- 一个包含 N 个顶点的完全图是 (N-1) 正则图。
证明：
在一个有 N 个顶点的完全图中，每个顶点都连接到其余所有 (N-1) 个顶点。因此，每个顶点的度数都是 (N-1)。所以，该图是 (N-1) 正则的。
- 对于一个 K 正则图，如果 K 是奇数，那么图中顶点的数量必须是偶数。
证明：
让我们假设顶点的数量 N 是奇数。
根据握手定理，我们知道：
所有顶点的度数之和 = 2 * 图的边数 …….(1)
方程 (1) 的右边是一个偶数。
对于 K 正则图，每个顶点的度数都是 K。所有顶点的度数之和 = K N，其中 K 和 N 都是奇数。因此它们的乘积（即所有顶点的度数之和）必须是奇数。这使得方程 (1) 的左边是一个奇数。所以左边 不等于* 右边。这意味着我们最初假设 N 是奇数是错误的。因此，顶点数量 (N) 必须是偶数。
- 环图 总是 2 正则的。
证明：
在环图 中，每个顶点都有两个邻居。因此，它们是 2 正则的。
- 2 正则图由 不相交的环的并集 和 无限链 组成。
- 一个具有 N 个顶点的 K 正则图，其边数 = (N*K)/2。
证明：
设一个具有 N 个顶点的 K 正则图的边数为 E。
根据握手定理，我们知道：
所有顶点的度数之和 = 2 * E
N K = 2 E
即，E = (N*K)/2
- 一个 K 维超立方体 是一个 K 正则图。
下图是一个 3 维超立方体(Q3)，它是一个 3 正则图。