G 的围长是指 G 中最短回路的长；若 G 没有回路，则定义 G 的围长为无穷大。 证明：围长为 4 的 k 正则图至少有 2k 个顶点，且恰有 2k 个顶点的这样的图（在同构意义下）只有一个。

我们可以先证明存在性，即存在一个围长为 4 的 k 正则图至少有 2k 个顶点。

考虑一个 k 正则图，它的围长为 4。我们可以假设这个图是简单图（即没有重边和自环）。由于围长为 4，任意两个顶点之间的距离都不超过 2。那么我们可以将这个图分成多个圆形的层，每层包含距离某个固定顶点距离为 i 的所有顶点。其中第 0 层只包含这个固定顶点自己，第 1 层包含与它直接相邻的顶点，第 2 层包含距离为 2 的顶点，以此类推。

由于这个图是 k 正则图，每个顶点的度数都是 k，所以每层的顶点数都是 k。那么这个图的总顶点数就是 $1 + 2k + 2(k-1) + 2(k-2) = 2k^2 - k + 1$。因为 k 正则图中的每个顶点都在 k 条边中出现一次，所以这个式子是一个整数。

接下来我们需要证明唯一性，即围长为 4 且顶点数为 2k 的 k 正则图只有一个。假设存在两个这样的图 G 和 H，它们的顶点集分别为 {a1, a2, ..., a2k} 和 {b1, b2, ..., b2k}。由于 G 和 H 都是 k 正则图，所以它们的度数序列相同。我们可以假设 $d(a_1) \leq d(a_2) \leq ... \leq d(a_{2k})$，$d(b_1) \leq d(b_2) \leq ... \leq d(b_{2k})$。

我们需要构造一个双射 f：{a1, a2, ..., a2k} → {b1, b2, ..., b2k}，使得对于所有的 i，$d(a_i) = d(f(a_i))$。我们可以通过归纳法来构造这个双射。

首先，我们可以找到两个度数相同的顶点 a 和 b，它们都有至少一个邻居 c 和 d，使得 c 和 d 的度数也相同。我们可以将 a 映射到 b，然后将 c 映射到 d。这样我们就构造出了一个双射，它满足 $d(a) = d(b)$ 且 $d(c) = d(d)$。

接下来我们需要考虑剩下的顶点。假设我们已经构造出了一个双射 f，使得对于前 i 个顶点，$d(a_j) = d(f(a_j))$（1 ≤ j ≤ i）。现在考虑第 i+1 个顶点 a。如果 $d(a) = d(a_{i+1})$，那么我们可以将 a 映射到 $f(a_{i+1})$。如果 $d(a) > d(a_{i+1})$，那么我们可以找到一个度数为 $d(a_{i+1})$ 的顶点 b，使得它还没有被映射，然后将 a 映射到 b。如果 $d(a) < d(a_{i+1})$，那么我们可以找到一个度数为 $d(a)$ 的顶点 b，使得它还没有被映射，然后将 b 映射到 $f(a_{i+1})$。

按照这种方法，我们可以构造出一个满足要求的双射 f。由于这个双射是由度数相同的顶点不断推出的，所以它保留了 k 正则图的很多性质。比如，如果两个顶点 a 和 b 之间有一条边，那么映射后的两个顶点 f(a) 和 f(b) 之间也有一条边。因此，我们可以通过这个双射将 G 映射到 H，同时将 H 映射到 G，从而证明它们同构。因此，围长为 4 且顶点数为 2k 的 k 正则图只有一个。