彼得森圖

彼得森(1839----1910)，丹麥哥本哈根大學數學教授。家境貧寒，因此而輟過學。但19歲就出版了關於對數的專著。他做過中學教師，32歲獲哥本哈根大學數學博士學位，然後一直在該大學作數學教授。

彼得森是一位出色的名教師。他講課遇到推理困難時，總是説：“這是顯而易見的”，並讓學生自己查閲他的著作。同時，他是一位有經驗的作家，論述問題很形象，講究形式的優雅。

1891年，彼得森發表了一篇奠定他圖論歷史地位的長達28頁的論文。這篇文章被公認是第一篇包含圖論基本結論的文章。同時也是第一次在文章中使用“圖”術語。

1898年，彼得森又發表了一篇只有3頁的論文，在這篇文章中，為舉反例構造了著名的彼得森圖。

雖然彼得森被認為是該圖的正式提出者，但實際上它最早出現於12年前，即A.B.Kempe（1886）的一篇論文中。Kempe觀察到，它的頂點可以代表Desargues構型的十條線，而它的邊則代表不在構型的十個點中的一個點相遇的線對。 ^[2] 

Petersen圖是一個軸對稱圖，且其各頂點具有輪換對稱性。

由於Petersen圖各點度數為3，顯然不滿足歐拉圖的充要條件——連通圖每點度數均為偶數。因此Petersen圖不是歐拉圖。

Petersen圖不是哈密爾頓圖（Hamilton Graph），即不含哈密爾頓迴路（Hamilton Cycle），但含240條不同的哈密爾頓路徑（Hamilton Path，即經過所有點一次且僅一次的路徑）。 ^[3] 

Petersen圖G滿足哈密爾頓圖的通常性質ω(G-S)≤|S|，即圖G去除一些頂點（這些定點的集合為S）後形成的新圖分支數小於等於S中頂點個數。但它並不是哈密爾頓圖，從而常常作為反例出現於圖論之中。

（反證）假設Petersen圖G = (V, E)是Hamilton圖，其Hamilton迴路為C = v₁v₂……v₁₀

|E(C)| = 10，則|E(G) - E(C)| = 5，即需要為C添加5條弦才能構成原Petersen圖G。接下來討論如何添加這5條弦。

claim 1：一條弦連接的兩個點在C上距離只能為4或5

（反證）由於Petersen圖最小環長度為5，若C上距離1，2，3的點之間有邊，會構成更小的環，矛盾；

又，C上兩點最大距離為5。故一條弦連接的兩個點在C上距離只能為4或5。

claim 2：至少有一條弦連接C上距離為4的兩個點

（反證）若5條弦均連接在C上距離為5的點，如圖2，則圖中有長度為4的環 v₁-v₂-v₇-v₆-v₁，矛盾。

claim 3：設弦e連接C上距離為4的兩個點，不失一般性設e = v₁v₅；則該弦兩端點在上的鄰居都不是弦的端點

與上同理，如果v₂或v₄或v₁₀或v₆連接某一條弦，則可構造出長度小於等於4的環；

綜上，e = v₁v₅，剩下可連接弦的點有v₃, v₇, v₈, v₉，又由於G中每點度數為3，即C上每點最多連接一條弦，故最多隻能再添加兩條弦；與|E(G) - E(C)| = 5矛盾。原命題得證。 ^[3] 

單位距離圖（unit-distance graph）的概念是，由由歐幾里得平面上的點的集合形成的圖，只要它們之間的距離正好是1，就將兩點連接起來。Petersen圖是單位距離圖，如圖5。 ^[3] 

Petersen圖不是平面圖，其交叉數（crossing number） ^[5]  為2，如圖6。 ^[3]  事實上Petersen圖是具有最小交叉數的立方圖。 ^[5] 

頂點連通數（vertex connectivity number）為圖的最小割點集大小 ^[6]  。Petersen圖的頂點連通數 κ(G) = 3，證明如下：

Petersen去掉任意一點，剩下的部分為Hamilton圖（亞哈密爾頓圖，見上）；再去掉一個點至多破壞其Hamilton環獲得一條Hamilton路徑；再去掉第三個點，至多破壞Hamilton路徑使圖不連通；因此最小割點集大小至少為3。而去掉三個點確實可以使Hamilton圖不連通。故其最小割點集大小為3。

獨立數（independence number）為圖的最大獨立集大小 ^[7]  。Petersen圖的最大獨立集大小 α(G) = 4——我們可以分別在內層和外層找兩個不相鄰的頂點，得到一個大小為4的獨立集；然而，如果我們想找到一個大小為5的頂點集，在外層或內層必須至少有3個頂點，而它們必然相連，故不存在大小為5的獨立集。

Desargues圖是頂點數為20，邊數為30的3 - 正則圖；為Petersen圖的推廣，如圖7。 ^[4]