佩特森圖

佩特森圖是一個特定的圖。朱利葉斯·佩特森在1898年構作它。雖然它以佩特森命名，但1886年已有人提及它了。

性質

交叉數為2

• 強正則圖
• 半徑同直徑均為2
• 點色數為3，邊色數為4。它是1898年至1946年期間，數學家唯一知道的snark。
• 非平面圖：子圖有完全圖$K_5$和完全雙分圖$K_{3,3}$，交叉數為2。
• 有哈密爾頓軌而無哈密爾頓圈。
• $KG_{5,2}$（Kneser圖）
• 单位距离图
• $K_5$的線圖的補圖
• 交叉数为2

最……

最小的snark

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

腳註

相關的维基共享资源：

佩特森圖