佩特森圖

此條目没有列出任何参考或来源。 (2010年8月16日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。

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

• 強正則圖。
• 半徑同直徑均為2。
• 点连通度和线连通度均为3。
• 最大独立集的大小为4。
• 點色數為3，邊色數為4。
• 非平面圖：子圖含有完全雙分圖${\displaystyle K_{3,3}}$的细分，交叉數為2。
• 有哈密頓路徑而無哈密顿圈。
• ${\displaystyle K_{5}}$的線圖的補圖。

• 最小無橋而邊色數大於3的三次圖（立方图）
• 最小無橋而沒有哈密爾頓圈的三次圖
• 最大半徑為2的三次圖
• 最小的hypohamiltonian圖（原本無哈密爾頓圈，但除去任何一個頂點，便可有哈密爾頓圈）
• 最小圍長為5的三次圖（唯一的${\displaystyle (3,5)}$-cage graph和唯一的${\displaystyle (3,5)}$-Moore graph。）

维基共享资源上的相关多媒体资源：佩特森圖