查看“︁佩特森圖”︁的源代码

{{unref|time=2010-08-16T11:01:34+00:00}}
[[File:Petersen graph.svg|right|200px]]

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

==性質==
[[File:Petersen graph, two crossings.svg|thumb|交叉數為2]]

* 強[[正則圖]]。
* 半徑同直徑均為2。
* 点连通度和线连通度均为3。
* 最大独立集的大小为4。
* [[图着色问题|點色數]]為3，邊色數為4。
* 非[[平面图 (图论)|平面圖]]：子圖含有[[完全雙分圖]]<math>K_{3,3}</math>的[[细分 (图论)|细分]]，交叉數為2。
* 有[[哈密頓路徑]]而無[[哈密顿圈]]。
* <math>K_5</math>的[[線圖]]的[[補圖]]。

==最……==
* 最小無橋而邊色數大於3的[[立方图|三次圖]]（立方图）
* 最小無橋而沒有哈密爾頓圈的三次圖
* 最大半徑為2的三次圖
* 最小的hypohamiltonian圖（原本無哈密爾頓圈，但除去任何一個[[顶点 (图论)|頂點]]，便可有哈密爾頓圈）
* 最小圍長為5的三次圖（唯一的<math>(3,5)</math>-[[cage graph]]和唯一的<math>(3,5)</math>-[[Moore graph]]。）

==腳註==
<references/>

{{Commonscat|Petersen graph}}
[[Category:正則圖]]