圍長 (圖論)

在图论中，一個圖的圍長定義為這個圖所包含的最短環長。 若這個圖是無環圖，它的圍長則定義做無窮大。 舉例來說，4-環（正方形）的圍長是 4。

籠 (Cage) 
最小的圍長為 g 的三次圖（3-正則圖）稱做 g-籠（或是 (3,g)-籠）。佩特森圖是唯一的 5-籠，Heawood graph 則是唯一的 6-籠，McGee graph 是唯一的 7-籠，Tutte eight cage 是唯一的 8-籠。 對特定的圍長來說，可能會存在不只一個籠。比如，存在三個不同構的 10-籠，分別都有 70 條邊：Balaban 10-cage、Harries graph、Harries–Wong graph。

圍長與圖染色 
給定任意正整數和，存在一幅圖，其圍長不小於，同時色數不小於。例如，無三角形，且色數為，然後重複採用構造法（格勒奇圖亦是以此法可得），即得任意大色數而無三角形的圖。埃尔德什·帕尔最先用證明一般的結論：

取個頂點的随机图，每兩點之間各自獨立地以概率連邊，則當趨向無窮時，大概率（趨向於）該圖中
長度不逾的環總數不超過，同時沒有大小的獨立集。所以，在每個短環中移除一點，餘下的子圖至少有點，圍長大於，但染色時，每種顏色的點數不能超過，即需要至少種色。

若不用概率論證，亦可明確構造圍長和色數皆大的圖，例如有限域上某些線性群的凱萊圖。此類例子同時屬，擴展系數大。

參考文獻