彼得森图

彼得森(1839----1910)，丹麦哥本哈根大学数学教授。家境贫寒，因此而辍过学。但19岁就出版了关于对数的专著。他作过中学教师，32岁获哥本哈根大学数学博士学位，然后一直在该大学作数学教授。

彼得森是一位出色的名教师。他讲课遇到推理困难时，总是说：“这是显而易见的”，并让学生自己查阅他的著作。同时，他是一位有经验的作家，论述问题很形象，讲究形式的优雅。

1891年，彼得森发表了一篇奠定他图论历史地位的长达28页的论文。这篇文章被公认是第一篇包含图论基本结论的文章。同时也是第一次在文章中使用“图”术语。

1898年，彼得森又发表了一篇只有3页的论文，在这篇文章中，为举反例构造了著名的彼得森图。

Petersen图G满足哈密尔顿图的通常性质ω(G-S)≤|S|，即图G去除一些顶点（这些定点的集合为S）后形成的新图分支数少于或等于S中元素的个数。但同时它并不是哈密尔顿图（但它有哈密顿路），这导致了它不同寻常的地位，从而常常作为反例出现在图论之中。

哈密尔顿图性质ω(G-S)≤|S|的证明：取出H图（哈密尔顿图的简称）的H圈C，G-S只比C-S多边，因而ω(G-S)≤ω(C-S)是显然的，而由于C是回路，删去k个顶点最多产生k个分支，ω(C-S)≤|S|也成立，得证。

Petersen图的顶点具有轮换对称性，即Petersen图是旋转对称的。并且，Petersen图的边也随着点一起对称。除此之外，Petersen图还是一个轴对称图。

• 顶点数v=10
• 边数e=15
• 分支数ω=1
• 各顶点的度为d(v)=3，因而它是三正则图（顶点的度只与之相连的边的数目）
• 围长C=5（一个图的围长是指它所包含的最短圈的周长，由于通过枚举可以发现Petersen图中无三圈与四圈，其围长为5）
• 直径d=2（一个图两点间的距离指其间最短路的长，而它的直径则指全图中最大的距离）^[1]

图1如图1，Petersen图的顶点可以如此分为三个部分，使各个部分中的点互不相连。因此，Petersen图是三部图。

设G = (V,E)是一个简单图，G*= (V,E*)是与图G相对应的完全图。 定义图G的补图H= (V,E') ，其中： E'= E*\E。当然图G与图H互为补图。而Petersen图的补图6正则图！这是非常漂亮的性质，而其正确性可以由它是3正则图直接导出。

• 哈密尔顿路有240条
• 无哈密尔顿回路（即非哈密尔顿图）
• 非欧拉图
• 非平面图
• 特征多项式(x-3)(x-1)⁵(x+2)⁴

图片(3)

Desargues图—Petersen图的推广

图2Desargues图如图2