graph theory

證明 Petersen graph 的圍長為 5

Prove or disprove that Petersen graph has girth 5.

Posted by blueskyson on November 12, 2021

Petersen graph 的定義：https://blueskyson.github.io/2021/11/12/petersen-graph/

Petersen graph 為 simple graph，故沒有 loop 與 multiple edge，也就是沒有 1-cycle 與 2-cycle，見下圖：
形成 3-cycle 需要 3 個所有元素都不重複的 2-set，這個條件無法用 5 個元素的集合來達成。
```
{1,2}, {3,4}, {5, ?} ====> 無法達成
```
4-cycle 不管怎麼湊，都會出現兩個一模一樣的 2-set，意味著出現了兩個重複的點，這違反了 Petersen graph 的基礎定義。
```
{1,2}, {3,4}, {1,5}, {3,4} ====> {3,4} 這個點重複了
```

舉一個 5-cycle 的例子：

{1,2}, {3,5}, {2,4}, {5,1}, {3,4} 形成一個 5-girth

由上述 4 個步驟得證 Petersen graph 的圍長 (girth) 為 5。