在图论的探索旅程中，我们首先需要明确一个概念：什么是图（Graph）？简单来说，图是由一组被称为顶点或节点的点，以及连接这些点对的边或弧的集合组成的。图的世界丰富多彩，包含多种类型，例如：
- 有向图
- 无向图
- 加权图
- 完全图
- 二分图
- 树
- 有环图
- 无环图
而彼得森图正是无向图领域中一种具有独特特征的代表。
让我们仔细看看彼得森图，它具备以下显著特征：
- 这是一个包含 10 个顶点和 15 条边的三次图（3-正则图）。
- 它是唯一的 (3,5)-笼图，也是唯一的 (3,5)-摩尔图。
- 它是参数为 3 的奇图，也是一种 Kneser 图，其中两个顶点相邻当且仅当它们对应的子集不相交。
- 它是完全图 K5 的线图的补图。
- 它是边数最少的无桥 3-正则图，且无法进行 3-边着色。
- 在所有拥有十个顶点的 3-正则图中，它的生成树数量最多，高达 2000 个。
值得注意的是，彼得森图中不存在 3-圈（三角形）或 4-圈。
!Peterson-Graph彼得森图
彼得森图的构造
我们可以把彼得森图看作是由半十二面体（Hemi-dodecahedron）的顶点和边构成的。所谓半十二面体，是一种将十二面体中相对的点、线和面进行合并识别后形成的几何结构。
广义彼得森图
如果我们有一个家族，其中的图是通过将正多边形的顶点与星形多边形的等价顶点连接起来而构成的，那么我们称这些图为广义彼得森图。通常，我们用符号 P(n, k) 来表示广义彼得森图。
!Peterson graphP(7,1)
举个例子，如果 n=7，k = 7/2 =3，我们就得到了 P(7,1)、P(7,2) 和 P(7,3)。
彼得森图的色数
观察上面的图示，我们可以发现它不是一个完全图。此外，由于图中包含奇数长度的环，这意味着它不是二分图。
虽然它不是二分图，但由于顶点的数量是偶数，彼得森图的色数实际上是 3。
!Peterson graph色数=3
其他特征：
- 它是一个 3-连通图，因此也是 3-边-连通的且没有桥。
- 它的色多项式为 t (t-1) (t-2) (t7-12t6+67t5-230t4+529t3-814t2+775t-352)
- 它是一个非平面图。
- 它不是哈密顿图。
- 彼得森图包含哈密顿路径，但没有哈密顿回路。
示例： 让我们来证明彼得森图不是哈密顿图。
!Peterson graph彼得森图
假设 G 是彼得森图，并假设相反地 G 是哈密顿图。我们用数字 A, B, C, D… J 来标记 G 的顶点。设 T = {AF, EJ, DI, CH, BG} 是 G 的边子集。那么 G − T 将是不连通的。因此，G 的任何哈密顿回路都必须包含 T 中的偶数条边。不难看出，任何只包含 T 中恰好两条边的回路都不可能是哈密顿回路。