圍長 (圖論)

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

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

• 
  The Petersen graph has a girth of 5
• 
  The Heawood graph has a girth of 6
• 
  The McGee graph has a girth of 7
• 
  The Tutte–Coxeter graph (Tutte eight cage) has a girth of 8

給定任意正整數${\displaystyle g}$和${\displaystyle \chi }$，存在一幅圖，其圍長不小於${\displaystyle g}$，同時色數不小於${\displaystyle \chi }$。例如，格勒奇圖（英语：Grötzsch graph）無三角形，且色數為${\displaystyle 4}$，然後重複採用梅切爾斯基（英语：Mycielskian）構造法（格勒奇圖亦是以此法可得），即得任意大色數而無三角形的圖。埃尔德什·帕尔最先用概率方法（英语：probabilistic method）證明一般的結論：^[4]

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

若不用概率論證，亦可明確構造圍長和色數皆大的圖，例如有限域上某些線性群的凱萊圖。^[5]此類例子同時屬拉馬努金圖（英语：Ramanujan graphs），擴展系數大。