佩特森图

此条目需要编修，以确保文法、用词、语气、格式、标点等使用恰当。 (2010年8月16日)
请按照校对指引，帮助编辑这个条目。（帮助、讨论）

Petersen graph.svg

彼得森图是一个由10个顶点和15条边构成的无向图。其最为人熟知的造型为一个五边形内包含一个五角星。彼得森图由丹麦哥本哈根大学数学教授Julius Peter Christian Petersen^[1]于1898年提出。由于其有趣的性质，它常常用于证明中的例子或反例。

性质

交叉数为2

强正则图。
半径同直径均为2。
点连通度和线连通度均为3。
最大独立集的大小为4。
点色数为3，边色数为4。
非平面图：子图有完全图 $K_{5}$ 和完全双分图 $K_{3,3}$ ，交叉数为2。
有哈密顿路径而无哈密顿圈。
$K_{5}$ 的线图的补图。

最……

最小无桥而边色数大于3的三次图（立方图）
最小无桥而没有哈密尔顿圈的三次图
最大半径为2的三次图
最小的hypohamiltonian图（原本无哈密尔顿圈，但除去任何一个顶点，便可有哈密尔顿圈）
最小围长为5的三次图（唯一的 $(3,5)$ -cage graph和唯一的 $(3,5)$ -Moore graph。）

脚注

^ Wikipedia Contributors. Julius Petersen. Wikipedia. [2020-12-25]. （原始内容存档于2021-02-11）.