Petersen 圖是具有 10 個頂點和 15 條邊的三次圖，它是唯一的 
-籠形圖 (Harary 1994, p. 175)，以及唯一的 
-穆爾圖。它可以構造為 
以步長 1 和 2 的圖展開，其中 
是一個 路徑圖 (Biggs 1993, p. 119)。切除 Petersen 圖的一條邊會得到 4-莫比烏斯梯子 
。上面在幾個嵌入中說明了它 (D'Angelo and Saaty and Kainen 1986; Harary 1994, p. 89; West 2000, p. 229; Knuth 2008, p. 39)。Petersen 圖也是 10-Lindgren-Sousselier 圖。
該圖由 Petersen (1898) 引入，作為邊著色問題的一個反例。然而，Kempe (1886) 早在十二年前就將其描述為頂點對應於 Desargues 配置 的點，邊對應於不位於配置線的點對的圖。以這種方式從配置產生的圖已被 Ed Pegg, Jr. 稱為普通（線）圖。（私人通訊，2024 年 9 月 11 日）。
Petersen 圖可以推廣，得到的圖被稱為 廣義 Petersen 圖 
，對於 
和 
。Petersen 圖對應於 
。
Petersen 圖的圍長為 5，直徑為 2，邊色數 為 4，色數 為 3，色多項式 為
Petersen 圖是一個 三次對稱圖，並且是非平面的。以下 D. West 的優美證明論證了 Petersen 圖是非哈密頓的。如果存在 10-圈 
，則該圖由 
加上五條弦組成。如果每條弦連線 
上相對的頂點，則存在 4-圈。因此，某條弦 
連線 
上距離為 4 的頂點。現在，沒有弦與 
在 
上的端點的相對頂點關聯，可以在不建立最多四個頂點的圈的情況下新增。因此，Petersen 圖是非哈密頓的。事實上，它也是最小的次哈密頓圖。
Petersen 圖是兩個在 10 個節點上具有最小可能圖交叉數 2 的三次圖之一（另一個是由 Pegg 和 Exoo 2009 表示的未命名圖 CNG 2B），使其成為最小三次交叉數圖 (Pegg 和 Exoo 2009, Clancy et al. 2019)。
Petersen 圖是在 10 個頂點上的唯一幾乎哈密頓三次圖 (Punnim et al. 2007)。事實上，它也是最大非哈密頓的 (Clark 和 Entringer 1983)。
它也是一個單位距離圖 (Gerbracht 2008)。
Petersen 圖是唯一沒有 Tait 著色的最小圍長圖。它是完全圖 
的線圖的補圖 (Skiena 1990, p. 139)，以及奇圖 
(Skiena 1990, p. 162)。
Petersen 圖是一個積分圖，其圖譜為 
。
Petersen 圖的二分雙圖是Desargues 圖。
Petersen 圖的線圖是四次頂點傳遞圖 Qt39，如上所示在幾個嵌入中說明。
Petersen 圖被描繪在期刊 Journal of Graph Theory 和 Discrete Mathematics 的封面上。它也是 Harary (1994) 封面右下角的圖。
Petersen 圖提供了射影平面的 6 著色。
Petersen 圖在 Wolfram 語言中實現為PetersenGraph[]，許多預計算屬性可透過以下方式獲得GraphData["PetersenGraph"].
下表總結了 Petersen 圖的一些屬性。
| 屬性 | 值 |
| 自同構群階 | 120 |
| 特徵多項式 |  |
| 色數 | 3 |
| 無爪圖 | 否 |
| 團數 | 2 |
| 圖補圖名稱 | 5-三角形圖 |
| 直徑 | 2 |
| 距離正則圖 | 是 |
| 邊色數 | 4 |
| 邊連通度 | 3 |
| 邊數 | 15 |
| 邊傳遞 | 是 |
| 尤拉圖 | 否 |
| 圍長 | 5 |
| 哈密頓圖 | 否 |
| 哈密頓圈計數 | 0 |
| 哈密頓路徑計數 | 240 |
| 次哈密頓圖 | 是 |
| 次可追蹤圖 | 否 |
| 積分圖 | 是 |
| 獨立數 | 4 |
| 線圖 | 否 |
| 線圖名稱 | 四次頂點傳遞圖 Qt39 |
| 完美圖 | 否 |
| 完美匹配圖 | 是 |
| 平面圖 | 否 |
| 多面體圖 | 否 |
| 半徑 | 2 |
| 正則圖 | 是 |
| 無平方圖 | 是 |
| 強正則圖 |  |
| 對稱圖 | 是 |
| 可追蹤圖 | 是 |
| 無三角形圖 | 是 |
| 頂點連通度 | 3 |
| 頂點數 | 10 |
| 頂點傳遞 | 是 |
參見
籠形圖,
廣義 Petersen 圖,
圍長,
Hoffman-Singleton 圖,
次哈密頓圖,
積分圖,
克內澤圖,
Lindgren-Sousselier 圖,
穆爾圖,
奇圖,
Petersen 圖族,
最小三次交叉數圖
使用 探索
參考文獻
Bondy, J. A. 和 Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236 和 243, 1976.Brouwer, A. E. "Petersen Graph." http://www.win.tue.nl/~aeb/drg/graphs/Petersen.html.Brouwer, A. E.; Cohen, A. M.; 和 Neumaier, A. Distance Regular Graphs. New York: Springer-Verlag, pp. 104 和 209, 1989.Clancy, K.; Haythorpe, M.; Newcombe, A.; 和 Pegg, E. Jr. "There Are No Cubic Graphs on 26 Vertices with Crossing Number 10 or 11." Preprint. 2019.Clark, L. 和 Entringer, R. "Smallest Maximally Nonhamiltonian Graphs." Periodica Math. Hungarica 14, 57-68, 1983.D'Angelo, J. P. 和 West, D. B. Mathematical Thinking: Problem-Solving and Proofs, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 2000.DistanceRegular.org. "Petersen Graph 
." http://www.distanceregular.org/graphs/petersen.html.Exoo, G. "Rectilinear Drawings of Famous Graphs: The Petersen Graph." http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/pete.gif.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. Nov. 15, 2008.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 89, 112, and 175, 1994.Hoffman, A. J. 和 Singleton, R. R. "On Moore Graphs of Diameter Two and Three." IBM J. Res. Develop. 4, 497-504, 1960.Holton, D. A. 和 Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Horvat, B. 和 Pisanski, T. "Unit Distance Representations of the Petersen Graph in the Plane." To appear in Ars Combin..Kempe, A. B. "A Memoir on the Theory of Mathematical Form." Philos. Trans. Royal Soc. London 177, 1-70, 1886.Knuth, D. E. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Functions and Boolean Functions.. Upper Saddle River, NJ: Addison-Wesley, 2008.Nedela, R. 和 Škoviera, M. "Which Generalized Petersen Graphs Are Cayley Graphs?" J. Graph Th. 19, 1-11, 1995.Pegg, E. Jr. 和 Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 161-170, 2009. https://www.mathematica-journal.com/data/uploads/2009/11/CrossingNumberGraphs.pdf.Petersen, J. "Sur la théorème de Tait." L'Intermédiare des Math. 5, 225-227, 1898.Punnim, N.; Saenpholphat, V.; 和 Thaithae, S. "Almost Hamiltonian Cubic Graphs." Int. J. Comput. Sci. Netw. Security 7, 83-86, 2007.Read, R. C. 和 Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 271 和 276, 1998.Royle, G. "F010A." http://www.csse.uwa.edu.au/~gordon/foster/F010A.html.Saaty, T. L. 和 Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 102, 1986.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 139, 162, and 191, 1990.Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, pp. 90-91, 2008.Steimle, A. 和 Staton, W. "The Isomorphism Classes of the Generalized Petersen Graphs." Disc. Math. 309, 231-237, 2009.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 225, 2000.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.
請引用本文為
Weisstein, Eric W. "Petersen 圖。" 來自 Web 資源。 https://mathworld.tw/PetersenGraph.html
學科分類
